Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Compressive Sensing For Sparsely Excited Speech Signals

Compressive sensing (CS) has been proposed for signals with sparsity in a linear transform domain. We explore a signal dependent unknown linear transform, namely the impulse response matrix operating on a sparse excitation, as in the linear model of speech production, for recovering compressive sensed speech. Since the linear transform is signal dependent and unknown, unlike the standard CS formulation, a codebook of transfer functions is proposed in a matching pursuit (MP) framework for CS recovery. It is found that MP is efficient and effective to recover CS encoded speech as well as jointly estimate the linear model. Moderate number of CS measurements and low order sparsity estimate will result in MP converge to the same linear transform as direct VQ of the LP vector derived from the original signal. There is also high positive correlation between signal domain approximation and CS measurement domain approximation for a large variety of speech spectra.

Coherent potential approximation, averaged T-matrix approximation and Lloyd's model

It is shown how the single-site coherent potential approximation and the averaged T-matrix approximation become exact in the calculation of the averaged single-particle Green function of the electron in the Anderson model when the site energy is distributed randomly with lorentzian distribution. Using these approximations, Lloyd's exact result is reproduced.

A new approach to thermochemical calculations of condensed fuel-oxidizer mixtures

A simple method of calculating the elemental stoichiometric coefficient, φe has been developed, which can easily be applied to multicomponent fuel-oxidizer compositions. The method correctly predicts whether a mixture is fuel lean, fuel rich, or stoichiometrically balanced. The total composition of oxidizing (or reducing) elements of the mixture appears to be related to the thermochemistry of the system. For the reaction of ammonium perchlorate and an organic fuel the heat of reaction varies linearly with the total composition of oxidizing elements. The physical significance of such a correlation based on thermochemical reasoning is highlighted in the paper.

The nonplanar peptide unit III. Quantum chemical calculations for related compounds and experimental X-ray diffraction data

The possible nonplanar distortions of the amide group in formamide, acetamide, N-methylacetamide, and N-ethylacetamide have been examined using CNDO/2 and INDO methods. The predictions from these methods are compared with the results obtained from X-ray and neutron diffraction studies on crystals of small open peptides, cyclic peptides, and amides. It is shown that the INDO results are in good agreement with observations, and that the dihedral angles N and defining the nonplanarity of the amide unit are correlated approximately by the relation N = -2, while C is small and uncorrelated with . The present study indicates that the nonplanar distortions at the nitrogen atom of the peptide unit may have to be taken into consideration, in addition to the variation in the dihedral angles (,), in working out polypeptide and protein structures.

Approximation of the perturbation equations of a quasi-linear hyperbolic system in the neighborhood of a bicharacteristic

In 1956 Whitham gave a nonlinear theory for computing the intensity of an acoustic pulse of an arbitrary shape. The theory has been used very successfully in computing the intensity of the sonic bang produced by a supersonic plane. [4.] derived an approximate quasi-linear equation for the propagation of a short wave in a compressible medium. These two methods are essentially nonlinear approximations of the perturbation equations of the system of gas-dynamic equations in the neighborhood of a bicharacteristic curve (or rays) for weak unsteady disturbances superimposed on a given steady solution. In this paper we have derived an approximate quasi-linear equation which is an approximation of perturbation equations in the neighborhood of a bicharacteristic curve for a weak pulse governed by a general system of first order quasi-linear partial differential equations in m + 1 independent variables (t, x1,…, xm) and derived Gubkin's result as a particular case when the system of equations consists of the equations of an unsteady motion of a compressible gas. We have also discussed the form of the approximate equation describing the waves propagating upsteam in an arbitrary multidimensional transonic flow.

Application of ab initio molecular orbital calculations to the structural moieties of carbohydrates. 3

Ab initio RHF/4-31G level molecular orbital calculations have been carried out on dimethoxymethane as a model compound for the acetal moiety in methyl pyranosides. The calculations are consistent with the predictions of the anomeric effect and the exo-anomeric effect. They reproduce very successfully the differences in molecular geometry observed by x-ray and neutron diffraction of single crystals of the methyl cy-D- and methyl 0-D-pyranosides. Calculations carried out at the 6-3 1G* level for methanediol confirm the earlier calculations at the 4-31G level, with smaller energy differences between the four staggered conformations.

Impulse Voltage Breakdown Characteristics of Point-Plane Gaps at Low Pressures

Practical applications of vacuum as an insulator necessitated determining the low-pressure breakdown characteristics of long gap lengths of a point-plane electrode system. The breakdown voltage has been found to vary as the square root of the gap length. Further, with the point electrode as the anode, the values of the breakdown voltages obtained have been found to be larger than those obtained with a plane-parallel electrode system at a corresponding gap length. By applying the theory of the anode heating mechanism as the cause for breakdown, the results have been justified, and by utilizing a field efficiency factor which is the ratio of the average to maximum field, an empirical criterion has been developed. This criterion helps in calculating the breakdown voltage of a nonuniform gap system by the knowledge of the breakdown voltage of a plane-parallel electrode system.

An appendix to the paper "approximation of the perturbation equations of a quasi-linear hyperbolic system in the neighborhood of a bicharacteristic"

The theory of Varley and Cumberbatch [l] giving the intensity of discontinuities in the normal derivatives of the dependent variables at a wave front can be deduced from the more general results of Prasad which give the complete history of a disturbance not only at the wave front but also within a short distance behind the wave front. In what follows we omit the index M in Eq. (2.25) of Prasad [2].

Theoretical calculations of base-base interactions in nucleic acids: II Stacking interactions in polynucleotides

Base-base interactions were computed for single- and double- stranded polynucleotides, for all possible base sequences. In each case, both right and left stacking arrangements are energetically possible. The preference of one over the other depends upon the base-sequence and the orientation of the bases with respect to helix-axis. Inverted stacking arrangement is also energetically possible for both single- and double-stranded polynucleotides. Finally, interaction energies of a regular duplex and the alternative structures3 were compared. It was found that the type II model3 is energetically more favourable than the rest.

Theoretical calculations of base-base interactions in nucleic acids: I Stacking interactions in free bases

Stacking interactions in free bases were computed on the basis of molecular association. The results of the calculations were compared with the stacking patterns observed in a few single crystals of nucleic acid components as examples. The following are the conclusions: (i) there can be two types of stacking pattern classified as normal and inverted types for any two interacting bases and both can be energetically favourable (ii) in both the types the stacking interaction is a combined effect of the overlap of the interacting bases and relative positions and orientations of the atomic centres of the two bases (iii) crystal symmetry and H-bonding interaction may influence stacking patterns.

Beyond fractional derivatives: local approximation of other convolution integrals

Dynamic systems involving convolution integrals with decaying kernels, of which fractionally damped systems form a special case, are non-local in time and hence infinite dimensional. Straightforward numerical solution of such systems up to time t needs O(t(2)) computations owing to the repeated evaluation of integrals over intervals that grow like t. Finite-dimensional and local approximations are thus desirable. We present here an approximation method which first rewrites the evolution equation as a coupled in finite-dimensional system with no convolution, and then uses Galerkin approximation with finite elements to obtain linear, finite-dimensional, constant coefficient approximations for the convolution. This paper is a broad generalization, based on a new insight, of our prior work with fractional order derivatives (Singh & Chatterjee 2006 Nonlinear Dyn. 45, 183-206). In particular, the decaying kernels we can address are now generalized to the Laplace transforms of known functions; of these, the power law kernel of fractional order differentiation is a special case. The approximation can be refined easily. The local nature of the approximation allows numerical solution up to time t with O(t) computations. Examples with several different kernels show excellent performance. A key feature of our approach is that the dynamic system in which the convolution integral appears is itself approximated using another system, as distinct from numerically approximating just the solution for the given initial values; this allows non-standard uses of the approximation, e. g. in stability analyses.

Consistent quaternion interpolation for objective finite element approximation of geometrically exact beam

We explore an isoparametric interpolation of total quaternion for geometrically consistent, strain-objective and path-independent finite element solutions of the geometrically exact beam. This interpolation is a variant of the broader class known as slerp. The equivalence between the proposed interpolation and that of relative rotation is shown without any recourse to local bijection between quaternions and rotations. We show that, for a two-noded beam element, the use of relative rotation is not mandatory for attaining consistency cum objectivity and an appropriate interpolation of total rotation variables is sufficient. The interpolation of total quaternion, which is computationally more efficient than the one based on local rotations, converts nodal rotation vectors to quaternions and interpolates them in a manner consistent with the character of the rotation manifold. This interpolation, unlike the additive interpolation of total rotation, corresponds to a geodesic on the rotation manifold. For beam elements with more than two nodes, however, a consistent extension of the proposed quaternion interpolation is difficult. Alternatively, a quaternion-based procedure involving interpolation of relative rotations is proposed for such higher order elements. We also briefly discuss a strategy for the removal of possible singularity in the interpolation of quaternions, proposed in [I. Romero, The interpolation of rotations and its application to finite element models of geometrically exact rods, Comput. Mech. 34 (2004) 121–133]. The strain-objectivity and path-independence of solutions are justified theoretically and then demonstrated through numerical experiments. This study, being focused only on the interpolation of rotations, uses a standard finite element discretization, as adopted by Simo and Vu-Quoc [J.C. Simo, L. Vu-Quoc, A three-dimensional finite rod model part II: computational aspects, Comput. Methods Appl. Mech. Engrg. 58 (1986) 79–116]. The rotation update is achieved via quaternion multiplication followed by the extraction of the rotation vector. Nodal rotations are stored in terms of rotation vectors and no secondary storages are required.

Network flow-control using asynchronous stochastic approximation

We propose several stochastic approximation implementations for related algorithms in flow-control of communication networks. First, a discrete-time implementation of Kelly's primal flow-control algorithm is proposed. Convergence with probability 1 is shown, even in the presence of communication delays and stochastic effects seen in link congestion indications. This ensues from an analysis of the flow-control algorithm using the asynchronous stochastic approximation (ASA) framework. Two relevant enhancements are then pursued: a) an implementation of the primal algorithm using second-order information, and b) an implementation where edge-routers rectify misbehaving flows. Next, discretetime implementations of Kelly's dual algorithm and primaldual algorithm are proposed. Simulation results a) verifying the proposed algorithms and, b) comparing the stability properties are presented.