Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Crystallographic characterization of the conformation of the 1-aminocyclohexane-1-carboxylic acid residue in simple derivatives and peptides

The crystal structures of 1-aminocyclohexane-1-carboxylic acid (H-Acc6-OH) and six derivatives (including dipeptides) have been determined. The derivatives are Boc-Acc6-OH, Boc-(Acc6)2-OH, Boc-L-Met-Acc6-OMe, ClCH2CO-Acc6-OH, p-BrC6H4CO-Acc6-OH oxazolone, and the symmetrical anhydride from Z-Acc6-OH, [(Z-Acc6)2O]. The cyclohexane rings in all the structures adopt an almost perfect chair conformation. The amino group occupies the axial position in six structures; the free amino acid is the only example where the carbonyl group occupies an axial position. The values determined for the torsion angles about the N–Cα(φ) and Cα–CO (ψ) bonds correspond to folded, potentially helical conformations for the Acc6 residue.

Convergence feedback and unstable low frequency oscillations in a simple coupled ocean‐atmosphere model

The role of convergence feedback on the stability of a coupled ocean‐atmosphere system is studied using model III of Hirst (1986). It is shown that the unstable coupled mode found by Hirst is greatly modified by the convergence feedback. If the convergence feedback strength exceeds a critical value, several new unstable intraseasonal modes are also introduced. These modes have very weak dependence on the wave number. These results may explain the behaviour of some coupled models and to some extent provide a mechanism for the observed aperiodicity of the El‐Nino and Southern Oscillation (ENSO) events.

Distribution of simple repetitive (TG/CA)n and (CT/AG)n sequences in human and rodent genomes

Sixteen million nucleotide sequence of genome of various organisms have been analysed to detect and study the extent of occurrence of simple repetitive sequences. Two sequence motifs (TG/CA)n and (CT/AG)n capable of adopting unusual DNA structures, left handed Z-conformation and triple-helical conformation respectively, are found to be abundant in rodent and human genomes, but almost completely absent in bacterial genome. (TG/CA)n and (CT/AG)n sequences are present mostly in the intron or 5'/3' flanking regions of the genes. The presence of such repeat motifs in genomic sequence of higher eukaryotes has been correlated with their possible functional significance in nucleosome organization, recombination and gene expression.

Geometrically simple linear weirs using circular quadrants

A detailed theoretical analysis of flow through a quadrant plate weir is made in the light of the generalized theory of proportional weirs, using a numerical optimization procedure. It is shown that the flow through the quadrant plate weir has a linear discharge-head relationship valid for certain ranges of head. It is shown that the weir is associated with a reference plane or datum from which all heads are reckoned.Further, it is shown that the measuring range of the quadrant plate weir can be considerably enhanced by extending the tangents to the quadrants at the terminals of the quadrant plate weir. The importance of this weir (when the datum of the weir lies below its crest) as an outlet weir for grit chambers is highlighted. Experiments show excellent agreement with the theory by giving a constant average coefficient of discharge.

C-H…O hydrogen bond mediated chain reversal in a peptide containing g-amino acid residue, determined directly from powder X-ray diffraction data

The finding that peptides containing -amino acid residues give rise to folding patterns hitherto unobserved in -amino acid peptides[1] has stimulated considerable interest in the conformational properties of peptides built from , and residues,[2] as the introduction of additional methylene (CH2) units into peptide chains provides further degrees of conformational freedom.

Propagation of quasi-simple waves in a compressible rotating atmosphere

A class of self-propagating linear and nonlinear travelling wave solutions for compressible rotating fluid is studied using both numerical and analytical techiques. It is shown that, in general, a three dimensional linear wave is not periodic. However, for some range of wave numbers depending on rotation, horizontally propagating waves are periodic. When the rotation ohgr is equal to $$\sqrt {(\gamma - 1)/(4\gamma )}$$ , all horizontal waves are periodic. Here, gamma is the ratio of specific heats. The analytical study is based on phase space analysis. It reveals that the quasi-simple waves are periodic only in some plane, even when the propagation is horizontal, in contrast to the case of non-rotating flows for which there is a single parameter family of periodic solutions provided the waves propagate horizontally. A classification of the singular points of the governing differential equations for quasi-simple waves is also appended.

A simplified method for the purification of riboflavin-binding protein from hen's egg yolk

A simple and efficient procedure for the purification of the riboflavin-binding protein from hen's egg yolk is described. This method involves the removal by exclusion of lipoproteins and subsequent fractionation of soluble yolk proteins held on a DEAE-cellulose column by a salt gradient which is followed by purification by gel filtration on Sephadex G-100. The protein thus isolated is homogeneous by various physicoehemical, immunological, and functional criteria.

A simple n-state model for water

A simple n-state configurational excitation model which takes into account the presence of weakly connected pentamer units in liquid water is proposed. The model has features of both the “continuum” and “mixture” models. Calculations based on this model satisfactorily account for the important, diagnostic thermodynamic properties of water such as the density maximum, fraction of monomers and so on.

A simple and inexpensive two channel boxcar integrator

A two-channel boxcar integrator with an analog to digital converter was constructed using integrated circuits wherever convenient. The digital output can be instantaneously displayed or displayed after accumulating many samplings in the totaliser. The totaliser mode provides averaging at the digitiser level and hence the integrator has an infinite holding time. When used in the double boxcar mode the instrument overcomes the problem of any base line instability.

Cubicity of Interval Graphs and the Claw Number

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b-dimensional cube is a Cartesian product l(1) x l(2) x ... x l(b), where each l(i) is a closed interval of unit length on the real line. The cub/city of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b-dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line-i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number psi(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least log(2) psi(G)]. In this article, we show that for an interval graph G log(2) psi(G)-]<= cub(G)<=log(2) psi(G)]+2. It is not clear whether the upper bound of log(2) psi(G)]+2 is tight: till now we are unable to find any interval graph with cub(G)> (log(2)psi(G)]. We also show that for an interval graph G, cub(G) <= log(2) alpha], where alpha is the independence number of G. Therefore, in the special case of psi(G)=alpha, cub(G) is exactly log(2) alpha(2)]. The concept of cubicity can be generalized by considering boxes instead of cubes. A b-dimensional box is a Cartesian product l(1) x l(2) x ... x l(b), where each I is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k-dimensional boxes. It is clear that box(G)<= cub(G). From the above result, it follows that for any graph G, cub(G) <= box(G)log(2) alpha]. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323-333, 2010

Polarization studies in electromagnetic scattering by small Solar-system particles

In remote-sensing studies, particles that are comparable to the wavelength exhibit characteristic features in electromagnetic scattering, especially in the degree of linear polarization. These features vary with the physical properties of the particles, such as shape, size, refractive index, and orientation. In the thesis, the direct problem of computing the unknown scattered quantities using the known properties of the particles and the incident radiation is solved at both optical and radar spectral regions in a unique way. The internal electromagnetic fields of wavelength-scale particles are analyzed by using both novel and established methods to show how the internal fields are related to the scattered fields in the far zone. This is achieved by using the tools and methods that were developed specifically to reveal the internal field structure of particles and to study the mechanisms that relate the structure to the scattering characteristics of those particles. It is shown that, for spherical particles, the internal field is a combination of a forward propagating wave with the apparent wavelength determined by the refractive index of the particle, and a standing wave pattern with the apparent wavelength the same as for the incident wave. Due to the surface curvature and dielectric nature of the particle, the incident wave front undergoes a phase shift, and the resulting internal wave is focused mostly at the forward part of the particle similar to an optical lens. This focusing is also seen for irregular particles. It is concluded that, for both spherical and nonspherical particles, the interference at the far field between the partial waves that originate from these concentrated areas in the particle interior, is responsible for the specific polarization features that are common for wavelength-scale particles, such as negative values and local extrema in the degree of linear polarization, asymmetry of the phase function, and enhancement of intensity near the backscattering direction. The papers presented in this thesis solve the direct problem for particles with both simple and irregular shapes to demonstrate that these interference mechanisms are common for all dielectric wavelength-scale particles. Furthermore, it is shown that these mechanisms can be applied to both regolith particles in the optical wavelengths and hydrometeors at microwave frequencies. An advantage from this kind of study is that it does not matter whether the observation is active (e.g., polarimetric radar) or passive (e.g., optical telescope). In both cases, the internal field is computed for two mutually perpendicular incident polarizations, so that the polarization characteristics can then be analyzed according to the relation between these fields and the scattered far field.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

On the holographic simulation of non-circular zone plates

New methods involving the manipulation of fundamental wavefronts (e.g., plane and spherical) with simple optical components such as pinholes and spherical lenses have been developed for the fabrication of elliptic, hyperbolic and conical holographic zone plates. Also parabolic zone plates by holographic techniques have been obtained for the first time. The performance behaviour of these zone plates has been studied. Further a phenomenological explanation is offered for the observed improved fringe contrast obtained with a spherical reference wave.