New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Edge Stabilities of Hexagonal Boron Nitride Nanoribbons: A First-Principles Study

We investigate the comparative stability of sp(2) bonded planar hexagonal boron nitride (h-BN) nanoribbon (BNNR) edges, using first principles calculations. We find that the pristine armchair edges have the highest degree of stability. Pristine zigzag edges are metastable, favoring planar reconstructions in the form of 5-7 rings] that minimizes the energy. Our investigation further reveals that the pristine zigzag edges can be stabilized against 5-7 reconstructions by passivating the dangling bonds at the edges by other elements, such as hydrogen (H) atoms. Electronic and magnetic properties of nanoribbons depend on the edge shapes and are strongly affected by edge reconstructions.

On Network-Error Correcting Convolutional Codes under the BSC Edge Error Model

Convolutional network-error correcting codes (CNECCs) are known to provide error correcting capability in acyclic instantaneous networks within the network coding paradigm under small field size conditions. In this work, we investigate the performance of CNECCs under the error model of the network where the edges are assumed to be statistically independent binary symmetric channels, each with the same probability of error pe(0 <= p(e) < 0.5). We obtain bounds on the performance of such CNECCs based on a modified generating function (the transfer function) of the CNECCs. For a given network, we derive a mathematical condition on how small p(e) should be so that only single edge network-errors need to be accounted for, thus reducing the complexity of evaluating the probability of error of any CNECC. Simulations indicate that convolutional codes are required to possess different properties to achieve good performance in low p(e) and high p(e) regimes. For the low p(e) regime, convolutional codes with good distance properties show good performance. For the high p(e) regime, convolutional codes that have a good slope ( the minimum normalized cycle weight) are seen to be good. We derive a lower bound on the slope of any rate b/c convolutional code with a certain degree.

Non-uniform slot injection (suction) or wall enthalpy into a steady nonsimilar compressible laminar boundary layer

Steady two-dimensional and axisymmetric compressible nonsimilar laminar boundary-layer flows with non-uniform slot injection (or suction) and non-uniform wall enthalpy have been studied from the starting point of the streamwise co-ordinate to the exact point of separation. The effect of different free stream Mach number has also been considered. The finite discontinuities arising at the leading and trailing edges of the slot for the uniform slot injection (suction) or wall enthalpy are removed by choosing appropriate non-uniform slot injection (suction) or wall enthalpy. The difficulties arising at the starting point of the streamwise co-ordinate, at the edges of the slot and at the point of separation are overcome by applying the method of quasilinear implicit finite difference scheme with an appropriate selection of finer step size along the streamwise direction. It is observed that the non-uniform slot injection moves the point of separation downstream but the non-uniform slot suction has the reverse effect. The increase of Mach number shifts the point of separation upstream due to the adverse pressure gradient. The increase of total enthalpy at the wall causes the separation to occur earlier while cooling delays it. The non-uniform total enthalpy at the wall (i.e., the cooling or heating of the wall in a slot) along the streamwise co-ordinate has very little effect on the skin friction and thus on the point of separation.

The structure of amorphous platinum disulfide as studied by anomalous x-ray-scattering

Anomalous X-ray scattering (AXS) has been applied to study the structure of amorphous platinum disulfide, Pt1-xS2, prepared by the precipitation process. The local atomic arrangement in amorphous Pt1-xS2 was determined by the least-squares variational method so as to reproduce the experimental differential interference function at the Pt L(III) absorption edge by the AXS method as well as the ordinary interference function by MoK alpha. The structural unit in amorphous Pt1-xS2 is found to be a PtS6 octahedron, similar to that in crystalline PtS2. These octahedra share both their corners and edges, while only edge-sharing linkages occur in crystalline PtS2.

Anomalous X-ray scattering study of local structures in the superionic conducting class (CuI)(0.3)(Cu2O)(0.35)(MoO3)(0.35)

The anomalous X-ray scattering (AXS) method using Cu and Mo K absorption edges has been employed for obtaining the local structural information of superionic conducting glass having the composition (CuI)(0.3)(Cu2O)(0.35)(MoO3)(0.35). The possible atomic arrangements in near-neighbor region of this glass were estimated by coupling the results with the least-squares analysis so as to reproduce two differential intensity profiles for Cu and Mo as well as the ordinary scattering profile. The coordination number of oxygen around Mo is found to be 6.1 at the distance of 0.187 nm. This implies that the MoO6 octahedral unit is a more probable structural entity in the glass rather than MoO4 tetrahedra which has been proposed based on infrared spectroscopy. The pre-peak shoulder observed at about 10 nm(-1) may be attributed to density fluctuation originating from the MoO6 octahedral units connected with the corner sharing linkage, in which the correlation length is about 0.8 nm. The value of the coordination number of I- around Cu+ is estimated as 4.3 at 0.261 nm, suggesting an arrangement similar to that in molten CuI.

Analysis of a long thick orthotropic circular cylindrical shell panel

An exact three-dimensional elasticity solution has been obtained for an infinitely long, thick transversely isotropic circular cylindrical shell panel, simply supported along the longitudinal edges and subjected to a radial patch load. Using a set of three displacement functions, the boundary value problem is reduced to Bessel's differential equation. Numerical results are presented for different thickness to mean radius ratios and semicentral angles of the shell panel. Classical and first-order shear deformation orthotropic shell theories have been examined in comparison with the present elasticity solution.

Experimental studies of a distorted turbulent spot in a three-dimensional flow

We report here on the results of a series of experiments carried out on a turbulent spot in a distorted duct to study the effects of a divergence with straight streamlines preceded by a short stretch of transverse streamline curvature, both in the absence of any pressure gradient. It is found that the distortion produces substantial asymmetry in the spot: the angles at which the spot cuts across the local streamlines are altered dramatically (in contradiction of a hypothesis commonly made in transition zone modelling), and the Tollmien-Schlichting waves that accompany the wing tips of the spot are much stronger on the outside of the bend than on the inside. However there is no strong effect on the internal structure of the spot and the eddies therein, or on such propagation characteristics as overall spread rate and the celerities of the leading and trailing edges. Both lateral streamline curvature and non-homogeneity of the laminar boundary layer into which the spot propagates are shown to be strong factors responsible for the observed asymmetry. It is concluded that these factors produce chiefly a geometric distortion of the coherent structure in the spot, but do not otherwise affect its dynamics in any significant way.

Noise-spike-induced escape in a bistable system driven by colored noise: Noise with long correlation times

An escape mechanism in a bistable system driven by colored noise of large but finite correlation time (tau) is analyzed. It is shown that the fluctuating potential theory [Phys. Rev. A 38, 3749 (1988)] becomes invalid in a region around the inflection points of the bistable potential, resulting in the underestimation of the mean first passage time at finite tau by this theory. It is shown that transitions at large but finite tau are caused by noise spikes, with edges rising and falling exponentially in a time of O(tau). Simulation of the dynamics of the bistable system driven by noise spikes of the above-mentioned nature clearly reveal the physical mechanism behind the transition.

Photocatalysis on Fine Powders of Perovskite Oxides

Fine powders of semiconductor oxides have been widely used as photocatalysts for many reactions. Among the various photocatalytic reactions, water splitting has been given much importance, since it is a promising chemical route for solar energy conversion. Perovskite oxides, in particular SrTiO, have been commonly used as photocatalysts because some of them can decompose H,O into H, and 0, without an external bias potential (1). In turn, this is because the conduction band (CB) edges of some of the perovskite oxides are more negative than the H+/H, energy level. Since the catalytic activity is related to the surface properties of the solids, fine powders rather than single crystals are used. Photocatalysis on fine powers can be conveniently discussed in three parts, viz. preparation, characterization and their catalytic activity. Presently, photo-decomposition of water using SrTiO, fine powders is discussed in greater detail, although other photocatalytic reactions on various perovskite oxides are also briefly dealt with.

Sponge phase transitions from a lattice model

We use Monte Carlo simulations to obtain thermodynamic functions and correlation functions in a lattice model we propose for sponge phases. We demonstrate that the surface-density correlation function dominates the scattering only along the symmetric-sponge (SS) to asymmetric-sponge (AS) phase boundary but not the boundary between the sponge-with-free-edges (SFE) and symmetric-sponge phases. At this second thermodynamic transition the scattering is dominated instead by an edge-density (or seam-density) correlation function. This prediction provides an unambiguous diagnostic for experiments in search of the SS-SFE transition.

Low electric field, easily reversible electrical set and reset processes in a Ge15Te83Si2 glass for phase change memory applications

We report here an easily reversible set-reset process in a new Ge15Te83Si2 glass that could be a promising candidate for phase change random access memory applications. The I-V characteristics of the studied sample show a comparatively low threshold electric field (E-th) of 7.3 kV/cm. Distinct differences in the type of switching behavior are achieved by means of controlling the on state current. It enables the observation of a threshold type for less than 0.7 mA beyond memory type (set) switching. The set and reset processes have been achieved with a similar magnitude of 1 mA, and with a triangular current pulse for the set process and a short duration rectangular pulse of 10 msec width for the reset operation. Further, a self-resetting effect is seen in this material upon excitation with a saw-tooth/square pulse, and their response of leading and trailing edges are discussed. About 6.5 x 10(4) set-reset cycles have been undertaken without any damage to the device. (C) 2011 American Institute of Physics. doi: 10.1063/1.3574659]

Some aspects of information processing in biological vision

An attempt is made to present some challenging problems (mainly to the technically minded researchers) in the development of computational models for certain (visual) processes which are executed with, apparently, deceptive ease by the human visual system. However, in the interest of simplicity (and with a nonmathematical audience in mind), the presentation is almost completely devoid of mathematical formalism. Some of the findings in biological vision are presented in order to provoke some approaches to their computational models, The development of ideas is not complete, and the vast literature on biological and computational vision cannot be reviewed here. A related but rather specific aspect of computational vision (namely, detection of edges) has been discussed by Zucker, who brings out some of the difficulties experienced in the classical approaches.Space limitations here preclude any detailed analysis of even the elementary aspects of information processing in biological vision, However, the main purpose of the present paper is to highlight some of the fascinating problems in the frontier area of modelling mathematically the human vision system.

Vortex sheet simulation of a plane �canonical� mixing layer

Discrete vortex simulations of the mixing layer carried out in the past have usually involved large induced velocity fluctuations, and thus demanded rather long time-averaging to obtain satisfactory values of Reynolds stresses and third-order moments. This difficulty has been traced here, in part, to the use of discrete vortices to model what in actuality are continuous vortex sheets. We propose here a novel two-dimensional vortex sheet technique for computing mixing layer flow in the limit of infinite Reynolds number. The method divides the vortex sheet into constant-strength linear elements, whose motions are computed using the Biot-Savart law. The downstream far-field is modelled by a steady vorticity distribution derived by application of conical similarity from the solution obtained in a finite computational domain. The boundary condition on the splitter plate is satisfied rigorously using a doublet sheet. The computed large-scale roll-up of the vortex sheet is qualitatively similar to experimentally obtained shadow-graphs of the plane turbulent mixing layer. The mean streamwise velocity profile and the growth rate agree well with experimental data. The presently computed Reynolds stresses and third-order moments are comparable with experimental and previous vortex-dynamical results, without using any external parameter (such as the vortex core-size) of the kind often used in the latter. The computed autocorrelations are qualitatively similar to experimental results along the top and bottom edges of the mixing layer, and show a well-defined periodicity along the centreline. The accuracy of the present computation is independently established by demonstrating negligibly small changes in the five invariants (including the Hamiltonian) in vortex dynamics.

A polynomial bound on the number of light cycles in an undirected graph

Let G be an undirected graph with a positive real weight on each edge. It is shown that the number of minimum-weight cycles of G is bounded above by a polynomial in the number of edges of G. A similar bound holds if we wish to count the number of cycles with weight at most a constant multiple of the minimum weight of a cycle of G.