Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Coupling of surface acoustic waves propagating in two separated piezoelectric media

The coupling of surface acoustic waves propagating in two separated piezoelectric media is studied using the perturbation theory of Auld. The results of the analysis are applied to two configurations using Bi12GeO20 and CdS crystals. It is found that the loss due to coupling is about 7 dB at 50 MHz in the cases of (111)-cut, [110]-prop. Bi12GeO20 and Y-cut, 60°-X prop. CdS combination. On étudie le couplage des ondes acoustiques de surface se propageant sur deux milieux piezo-eléctriques par la théorie de perturbation de Auld. Les resultats d'analyse sont appliqué's aux deux configurations des cristanx Bi12GeO20 et CdS. On trouve que la perte par couplage est environ de 7 dB a 50 MHz dans le cas de combination de (111)-coupe, [110]-prop. Bi12GeO20 et Y-coupe, 60°-X prop. CdS.

A study of the spectrum of an acoustic field in shallow water due to noise sources at the surface

An expression for the spectrum and cross spectrum of an acoustic field measured at two vertically separated sensors in shallow water has been obtained for any correlated noise sources distributed over the surface. Numerical results are presented for the case where the noise sources, white noise and wind-induced colored noise, are contained within a circular disk centered over the sensors. The acoustic field is generally inhomogeneous except when the channel is deep. The coherence function becomes real for a large disk, for a radius greater than 25 times the depth of the channel, decreases with further increase of the size of the disk, and finally tapers off after certain limiting size, approximately given by 1/alpha, where alpha is the attenuation coefficient.

Probability Distribution of the Eigenvalues of the Random String Equation

The probability distribution of the eigenvalues of a second-order stochastic boundary value problem is considered. The solution is characterized in terms of the zeros of an associated initial value problem. It is further shown that the probability distribution is related to the solution of a first-order nonlinear stochastic differential equation. Solutions of this equation based on the theory of Markov processes and also on the closure approximation are presented. A string with stochastic mass distribution is considered as an example for numerical work. The theoretical probability distribution functions are compared with digital simulation results. The comparison is found to be reasonably good.

Search on a hypercubic lattice using a quantum random walk. I. d > 2

Random walks describe diffusion processes, where movement at every time step is restricted to only the neighboring locations. We construct a quantum random walk algorithm, based on discretization of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, that is, to find a marked vertex on a d-dimensional hypercubic lattice. The restriction on movement hardly matters for d > 2, and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the d -> infinity limit). In particular, the scaling behavior for d = 3 is only about 25% higher than the optimal d -> infinity value.

Search on a hypercubic lattice using a quantum random walk. II. d = 2

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d = 2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an O(root N ln N) algorithm, which is not optimal. The scaling behavior can be improved to O(root N ln N) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

Improved retrieval of aerosol size-resolved properties from moderate resolution imaging spectroradiometer over India: Role of aerosol model and surface reflectance

We have compared the total as well as fine mode aerosol optical depth (tau and tau(fine)) retrieved by Moderate Resolution Imaging Spectroradiometer (MODIS) onboard Terra and Aqua (2001-2005) with the equivalent parameters derived by Aerosol Robotic Network (AERONET) at Kanpur (26.45 degrees N, 80.35 degrees E), northern India. MODIS Collection 005 (C005)-derived tau(0.55) was found to be in good agreement with the AERONET measurements. The tau(fine) and eta (tau(fine)/tau) were, however, biased low significantly in most matched cases. A new set of retrieval with the use of absorbing aerosol model (SSA similar to 0.87) with increased visible surface reflectance provided improved tau and tau(fine) at Kanpur. The new derivation of eta also compares well qualitatively with an independent set of in situ measurements of accumulation mass fraction over much of the southern India. This suggests that though MODIS land algorithm has limited information to derive size properties of aerosols over land, more accurate parameterization of aerosol and surface properties within the existing C005 algorithm may improve the accuracy of size-resolved aerosol optical properties. The results presented in this paper indicate that there is a need to reconsider the surface parameterization and assumed aerosol properties in MODIS C005 algorithm over the Indian region in order to retrieve more accurate aerosol optical and size properties, which are essential to quantify the impact of human-made aerosols on climate.

Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs

Let n points be placed independently in d-dimensional space according to the density f(x) = A(d)e(-lambda parallel to x parallel to alpha), lambda, alpha > 0, x is an element of R-d, d >= 2. Let d(n) be the longest edge length of the nearest-neighbor graph on these points. We show that (lambda(-1) log n)(1-1/alpha) d(n) - b(n) converges weakly to the Gumbel distribution, where b(n) similar to ((d - 1)/lambda alpha) log log n. We also prove the following strong law for the normalized nearest-neighbor distance (d) over tilde (n) = (lambda(-1) log n)(1-1/alpha) d(n)/log log n: (d - 1)/alpha lambda <= lim inf(n ->infinity) (d) over tilde (n) <= lim sup(n ->infinity) (d) over tilde (n) <= d/alpha lambda almost surely. Thus, the exponential rate of decay alpha = 1 is critical, in the sense that, for alpha > 1, d(n) -> 0, whereas, for alpha <= 1, d(n) -> infinity almost surely as n -> infinity.

A molecular dynamics study of cage-to-cage migration in sodium Y zeolite: role of surface-mediated diffusion

The details of cage-to-cage migration have been obtained from an analysis of the molecular dynamics trajectory of a probe adsorbate. It is observed that particles utilize the region within a radius of 2 angstrom from the window center but with diffusion taking place predominantly at 1.6 angstrom from the window center and a potential energy of nearly -12 kJ/mol. A barrier of about 0.5 kJ/mol is observed for surface-mediated diffusion. Surprisingly, for diffusion without surface mediation for a particle going from one cage center to another, there is an attractive well near the window instead of a barrier. At low adsorbate concentrations and room temperature, the predominant mode for cage-to-cage migration is surface-mediated diffusion. The analysis suggests that particles slide along the surface of the inner walls of the alpha-cages during migration from one cage to another.

Application of novel method for surface-ray tracing over hyperboloidal scatterers

A novel geodesic constant method has been developed for the hitherto unsolved problem of surface-ray tracing over a class of surface, namely the general hyperboloid of revolution (GHOR). All the ray-geometric parameters are obtained analytically in a one-parameter form. The ray parameters derived here for the first time can be readily used in the UTD formulation for computing the mutual coupling between the antennas located on the GHOR.

Impact of water drops onto the junction of a hydrophobic texture and a hydrophilic smooth surface

Wettability gradient surfaces play a significant role in control and manipulation of liquid drops. The present work deals with the analysis of water drops impacting onto the junction line between hydrophobic texture and hydrophilic smooth portions of a dual-textured substrate made using stainless steel material. The hydrophobic textured portion of the substrate comprised of unidirectional parallel groove-like and pillar-like structures of uniform dimensions. A high-speed video camera recorded the spreading and receding dynamics of impacting drops. The drop impact dynamics during the early inertia driven impact regime remains unaffected by the dual-texture feature of the substrate. A larger retraction speed of drop liquid observed on the hydrophobic portion of the substrate during the impact of low velocity drops makes the drop liquid on the higher wettability portion to advance further (secondary drop spreading). The net horizontal drop velocity towards the hydrophilic portion of the dual-textured substrate decreases with increasing drop impact velocity. The available experimental results suggest that the movement of bulk drop liquid away from the impact point during drop impact on the dual-textured substrate is larger for the impact of low inertia drops. (C) 2010 Elsevier B.V. All rights reserved.

Effect of V2O5 on the Surface and Structural Characteristics of Potassium Lithium Niobate

It has been suggested that materials with interesting and useful bulk non-linear optical properties might result by substituting vanadium, the lightest element in the group V of periodic table, for Nb or Ta atoms along with Li and three oxygens. It is with this motivation that we have been making attempts to grow single crystals of LiNbO3 doped with various concentrations of V2O5. Unfortunately the results obtained on the ceramic samples of this material have not been very encouraging, owing to their hygroscopic nature. However, our attempts to prepare both ceramic and single-crystalline samples of potassium lithium niobate (K3Li2Nb5O15; KLN) doped V2O5 were successful. In this letter we report the preliminary results concerning our studies on the effect of V2O5 doping on the structural as well as topographic features of both ceramic and single-crystalline samples of KLN.