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.

2 Algorithms For 3-Layer Channel Routing

A channel router is an important design aid in the design automation of VLSI circuit layout. Many algorithms have been developed based on various wiring models with routing done on two layers. With the recent advances in VLSI process technology, it is possible to have three independent layers for interconnection. In this paper two algorithms are presented for three-layer channel routing. The first assumes a very simple wiring model. This enables the routing problem to be solved optimally in a time of O(n log n). The second algorithm is for a different wiring model and has an upper bound of O(n2) for its execution time. It uses fewer horizontal tracks than the first algorithm. For the second model the channel width is not bounded by the channel density.

Boundary layer transition observations on a body of revolution with surface heating and cooling in water

Boundary layer flow visualization in water with surface heat transfer was carried out on a body of revolution which had the predicted possibility of laminar separation under isothermal conditions. Flow visualization was by in-line holographic technique. Boundary layer stabilization, including elimination of laminar separation, was observed to take place on surface heating. Conversely, boundary layer destabilization was observed on surface cooling. These findings are consistent with the theoretical predictions of Wazzan et al. in The stability and transition of heated and cooled incompressible laminar boundary layers, in Proceedings of the Fourth International Heat Transfer Conference, Vol. 2, FCI 4. Elsevier, Amsterdam (1970).

A study on the nature of the compound layer formed during the ion nitriding of En40B steel

Commercial-grade En40B steel has been ion nitrided in the temperature range 475–550°C in a 25%N2–75%H2 gas mixture. The nature of the compound layer formed was studied by the X-ray diffraction technique and optical metallography. It was observed that the structure of the compound layer gradually transforms from a predominantly epsilon (Porson) nitride to a predominantly γ′ nitride structure with increasing treatment time. Optical metallography studies on sections orthogonal to the nitrided surface showed that, after about 5 h of treatment, the thickness of the compound layer decreases with further increase in treatment time.

Configuration mixing in the s-hole states of metal ions

Configuration interaction calculation have been carried out on the s-hole states of Mn2+ Fe2+ (both high- and low-spin configurations). Co2+, Ca2+, K+ and Na+ including configurations involving virtual orbitals. The results show good agreement with the multiplet structures found in X-ray photoelectron spectra of these ions.

The harmonic torsional oscillations of a thin disk submerged in a fluid with a surfactant surface layer

A formulation in terms of a Fredholm integral equation of the first kind is given for the axisymmetric problem of a disk oscillating harmonically in a viscous fluid whose surface is contaminated with a surfactant film. The equation of the first kind is converted to a pair of coupled integral equations of the second kind, which are solved numerically. The resistive torque on the disk is evaluated and surface velocity profiles are computed for varying values of the ratio of the coefficient of surface shear viscosity to the coefficient of viscosity of the substrate fluid, and the depth of the disk below the surface.

R-parameter: A local truncation error based adaptive framework for finite volume compressible flow solvers

A residual-based strategy to estimate the local truncation error in a finite volume framework for steady compressible flows is proposed. This estimator, referred to as the -parameter, is derived from the imbalance arising from the use of an exact operator on the numerical solution for conservation laws. The behaviour of the residual estimator for linear and non-linear hyperbolic problems is systematically analysed. The relationship of the residual to the global error is also studied. The -parameter is used to derive a target length scale and consequently devise a suitable criterion for refinement/derefinement. This strategy, devoid of any user-defined parameters, is validated using two standard test cases involving smooth flows. A hybrid adaptive strategy based on both the error indicators and the -parameter, for flows involving shocks is also developed. Numerical studies on several compressible flow cases show that the adaptive algorithm performs excellently well in both two and three dimensions.

Theoretical study of a 16-µm CO2 downstream-mixing gasdynamic laser: A two-dimensional approach

A 16-µm CO2-N2 downstream-mixing gasdynamic laser, where a cold CO2 stream is mixed with a vibrationally excited N2 stream at the exit of the nozzle, is studied theoretically. The flow field is analyzed using a two-dimensional, unsteady, laminar and viscous flow model including appropriate finite-rate vibrational kinetic equations. The analysis showed that local small-signal gain up to 21.75 m−1 can be obtained for a N2 reservoir temperature of 2000 K and a velocity ratio of 1:1 between the CO2 and N2 mixing streams. Applied Physics Letters is copyrighted by The American Institute of Physics.

EPR studies on donor doped BaTiO3 grain boundary layer ceramic dielectrics

Donor doped BaTiO3 ceramics become insulating5 under controlled conditions with effective dielectric constants >10. The changes in EPR signals indicate that a certain fraction of the donor doped BaTiO3 is cubic even at room temperature and that the cubic fraction increases with the donor content. X-ray powder diffraction data support the EPR results. The coexistence of both the phases over a range of temperature is characteristic of diffused phase transition. The effect of grain size variation on EPR signal intensities indicate that the boundary layers surrounding the grains may constitute the cubic phase as a result of higher Ba-vacancies and donor contents at the grain boundary layer than in the bulk. Since the acceptor states arising from the Ba-vacancies and the impurities are activated in the cubic phase, they capture electrons from the conduction band, rendering the cubic phase electrically more insulating than the semiconductive tetragonal grain interiors. Thus, the cubic grain boundary layers act as effective dielectric media where the field tends to concentrate.

X-ray studies on crystalline complexes involving amino acids. IV. The structure of L-arginine L-ascorbate

L-Arginine ascorbate, C6HIsN40+.C6H706, a 1"1 crystalline complex between the amino acid arginineand the vitamin ascorbic acid, crystallizes in the monoclinic space group P21 with two formula units in a cell of dimensions a = 5.060 (8), b = 9.977 (9), c = 15.330 (13) A, fl = 97.5 (2) °. The structure was solved by the symbolic addition procedure and refined to an R of 0.067 for 1501 photographically observed reflec- tions. The conformation of the arginine molecule in the structure is different from any observed so far. The present structure provides the first description of the ascorbate anion unaffected by the geometrical constraints and disturbances imposed by the requirements of metal coordination. The lactone group and the deprotonated enediol group in the anion are planar and the side chain assumes a conformation which appears to be sterically the most favourable. In the crystals, the arginine molecules and the ascorbate anions aggregate separately into alternating layers. The molecules in the arginine layer are held together by interactions involving a-amino and ~t-carboxylate groups, a situation analogous to that found in proteins. The two layers of unlike molecules are interconnected primarily through the interactions of the side-chain guanidyl group of arginine with the ascorbate ion. These involve a specific ion-pair interaction accompanied by two convergent hydrogen bonds and another pair of nearly parallel hydrogen bonds.

Solutions of Boundary Layer Equations Governing Free Convective and Magnetohydrodynamic Flows through Parametric Differentiation

In der vorliegenden Arbeit wird die Methode der parametrischen Differentiation angewendet, um ein System nichtlinearer Gleichungen zu lösen, das zwei- und dreidimensionale freie, konvektive Grenzschichströmungen bzw. eine zweidimensionale magnetohydrodynamische Grenzschichtströmung beherrscht. Der Hauptvorteil dieser Methode besteht darin, daß die nichlinearen Gleichungen auf lineare reduziert werden und die Nichtlinearität auf ein System von Gleichungen erster Ordnung beschränkt wird, das, verglichen mit den ursprünglichen Nichtlinearen Gleichungen, viel leichter gelöst werden kann. Ein anderer Vorzug der Methode ist, daß sie es ermöglicht, die Lösung von einer bekannten, zu einem bestimmten Parameterwert gehörigen Lösung aus durch schrittweises Vorgehen die Lösung für den gesamten Parameterbereich zu erhalten. Die mit dieser Methode gewonnenen Ergebnisse stimmen gut mit den entsprechenden, mit anderen numerischen Verfahren erzielten überein.

Long waves in inviscid compressible atmosphere II

Solitary waves have been found in an adiabatic compressible atmosphere which, in ambient state, has winds and temperature gradient, generalizing our earlier results for the isothermal atmosphere. Explicit results are obtained for the special case of linear temperature and linear wind distributions in the undisturbed conditions. An important result of the study is that the number of possible critical speeds of the flow depends crucially on whether the maximum Richardson number (which is variable in the present example) is greater or less than 1/4.

The non-planar peptide unit II. Comparison of theory with crystal structure datastar, open

The theoretical results derived in Part I (Ramachandran, G.N., Lakshminarayan, A.V. and Kolaskar, A.S. (1973) Biochim. Biophys. Acta 303, 8–13) that the three bonds of the peptide unit meeting at N can have a pyramidal structure is confirmed by an analysis of 14 published crystal structures of small peptides. It is shown that the dihedral angles θN and Δω are correlated, while θC, is small and is uncorrelated with Δω, showing that the non-planar distortion at C′ is generally small.

Theory of the non-planar peptide unitstar, open

By means of CNDO/2 calculations on N-methyl acetamide, it is shown that the state of minimum energy of the trans-peptide unit is a non-planar conformation, with the NH and NC2α bonds being significantly out of the plane formed by the atoms C1α, C′, O and N.

Layer-by-layer self-assembly of modified hyaluronic acid/chitosan based on hydrogen bonding

The fabrication of hydrogen bonded polymer self-assembly for drug delivery has been accomplished via layer-by-layer sequential assembly from aqueous solution. In this study, the self-assembly was constructed based on hydrogen bonding between DNA base (adenine and thymine) pairs substituted on the backbone of chitosan and hyaluronic acid. Chitosan was modified with adenine, whereas hyaluronic acid was modified with thymine. Subsequently, these two polymers were sequentially absorbed on flat substrate by taking advantage of interactions of DNA base pairs via hydrogen bonding. Interlayer hydrogen bonding of these two polymers produces stable multilayer film without using any cross-linking agent. Thin film formation on quartz substrate has been monitored with UV-vis spectra and an AFM study. Formation of multilayer hydrogen-bonded thin film has been further confirmed with SEM. Encapsulation and release behavior of the therapeutic drug from the multilayer thin film at different conditions has been illustrated using UV-vis spectra. Cell viability of modified polymers using MTT assay confirmed no cytotoxic effect.