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.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

A note on the effective medium theory of random resistive-reactive medium

The effective medium theory for a system with randomly distributed point conductivity and polarisability is reformulated, with attention to cross-terms involving the two disorder parameters. The treatment reveals a certain inconsistency of the conventional theory owing to the neglect of the Maxwell-Wagner effect. The results are significant for the critical resistivity and dielectric anomalies of a binary liquid mixture at the phase separation point.

Dilute Solution Properties of Methyl Methacrylate/Acrylonitrile Random Copolymers, 2a)

The Stockmayer-Fixman relation was used to evaluate the short range and long range interaction parameters for methyl methacrylate/acrylonitrile copolymers of 0,566 and 0,657 mole fraction of monomeric units of acrylonitrile in the solvents acetonitrile, 2-butanone, dimethyl formamide, and y-butyrolactone, at different temperatures (30, 45, and 60 “C). The values of KO were found to be lower than those of the parent homopolymers, and their values depend on both solvent and temperature. Even negative Ko-values were obtained, in cases in which the Mark Houwink exponent a is nearly unity. The values of the polymer-solvent interaction parameter, x, , are high and close to 0,5, indicating that these solvents are not good. The values of the excess interaction parameter, xAB, are negative and are not affected by temperature. The large extension of these copolymer chains, as exhibited by a and a;-values, can be understood in terms of unusual short range interactions only. Similar results were obtained for some cellulose derivatives.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Multi-state-choice automata model for expedient learning in random environment

A new automata model Mr,k, with a conceptually significant innovation in the form of multi-state alternatives at each instance, is proposed in this study. Computer simulations of the Mr,k, model in the context of feature selection in an unsupervised environment has demonstrated the superiority of the model over similar models without this multi-state-choice innovation.

Random vibration of a second order non-linear elastic system

A method is presented for obtaining, approximately, the response covariance and probability distribution of a non-linear oscillator under a Gaussian excitation. The method has similarities with the hierarchy closure and the equivalent linearization approaches, but is different. A Gaussianization technique is used to arrive at the output autocorrelation and the input-output cross-correlation. This along with an energy equivalence criterion is used to estimate the response distribution function. The method is applicable in both the transient and steady state response analysis under either stationary or non-stationary excitations. Good comparison has been observed between the predicted and the exact steady state probability distribution of a Duffing oscillator under a white noise input.

Optimal maintenance policy for equipment subject to random deterioration and random failure A modern control theory approach.

The stochastic version of Pontryagin's maximum principle is applied to determine an optimal maintenance policy of equipment subject to random deterioration. The deterioration of the equipment with age is modelled as a random process. Next the model is generalized to include random catastrophic failure of the equipment. The optimal maintenance policy is derived for two special probability distributions of time to failure of the equipment, namely, exponential and Weibull distributions Both the salvage value and deterioration rate of the equipment are treated as state variables and the maintenance as a control variable. The result is illustrated by an example

Sequence distribution in Acrylonitrile-methylacrylate random copolymers by N.M.R spectroscopy

The sequence distribution studies on the acrylonitrile-methylmethacrylate copolymer of high methylmethacrylate (M) content (30%

Effect of creep deformations in mechanical systems under combined deterministic and random inputs

The effect of creep on the vibrations of a single degree of freedom system subjected to combined random and deterministic excitation has been studied in this paper. The deterministic part of the excitation is assumed to be a sinusoidal function while the random part of the excitation is considered as a narrow band process with a central frequency equal to the frequency of sinusoidal part of the excitation. Creep, an energy absorbing process, introduces an equivalent damping into the system. A measure of this damping and the statistical properties of the response of the mechanical system have been derived.

A conditional random field-based downscaling method for assessment of climate change impact on multisite daily precipitation in the Mahanadi basin

Downscaling to station-scale hydrologic variables from large-scale atmospheric variables simulated by general circulation models (GCMs) is usually necessary to assess the hydrologic impact of climate change. This work presents CRF-downscaling, a new probabilistic downscaling method that represents the daily precipitation sequence as a conditional random field (CRF). The conditional distribution of the precipitation sequence at a site, given the daily atmospheric (large-scale) variable sequence, is modeled as a linear chain CRF. CRFs do not make assumptions on independence of observations, which gives them flexibility in using high-dimensional feature vectors. Maximum likelihood parameter estimation for the model is performed using limited memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) optimization. Maximum a posteriori estimation is used to determine the most likely precipitation sequence for a given set of atmospheric input variables using the Viterbi algorithm. Direct classification of dry/wet days as well as precipitation amount is achieved within a single modeling framework. The model is used to project the future cumulative distribution function of precipitation. Uncertainty in precipitation prediction is addressed through a modified Viterbi algorithm that predicts the n most likely sequences. The model is applied for downscaling monsoon (June-September) daily precipitation at eight sites in the Mahanadi basin in Orissa, India, using the MIROC3.2 medium-resolution GCM. The predicted distributions at all sites show an increase in the number of wet days, and also an increase in wet day precipitation amounts. A comparison of current and future predicted probability density functions for daily precipitation shows a change in shape of the density function with decreasing probability of lower precipitation and increasing probability of higher precipitation.

Underwater Sustainability of the ``Cassie'' State of Wetting

A rough hydrophobic surface when immersed in water can result in a ``Cassie'' state of wetting in which the water is in contact with both the solid surface and the entrapped air. The sustainability of the entrapped air on such surfaces is important for underwater applications such as reduction of flow resistance in microchannels and drag reduction of submerged bodies such as hydrofoils. We utilize an optical technique based oil total internal reflection of light at the water-air interface to quantify the spatial distribution of trapped air oil such a surface and its variation with immersion time. With this technique, we evaluate the sustainability of the Cassie state on hydrophobic surfaces with four different kinds of textures. The textures studied are regular arrays of pillars, ridges, and holes that were created in silicon by a wet etching technique, and also a texture of random craters that was obtained through electrodischarge machining of aluminum. These surfaces were rendered hydrophobic with a self-assembled layer Of fluorooctyl trichlorosilane. Depending on the texture, the size and shape of the trapped air pockets were found to vary. However, irrespective of the texture, both the size and the number of air pockets were found to decrease with time gradually and eventually disappear, suggesting that the sustainability of the ``Cassie'' state is finite for all the microstructures Studied. This is possibly due to diffusion of air from the trapped air pockets into the water. The time scale for disappearance of air pockets was found to depend on the kind of microstructure and the hydrostatic pressure at the water-air interface. For the surface with a regular array of pillars, the air pockets were found to be in the form of a thin layer perched on top of the pillars with a large lateral extent compared to the spacing between pillars. For other surfaces studied, the air pockets are smaller and are of the same order as the characteristic length scale of the texture. Measurements for the surface with holes indicate that the time for air-pocket disappearance reduces as the hydrostatic pressure is increased.

The non-linear response of a gyrostabilized platform: Effects of correction torque time delay and of random inputs

First, the non-linear response of a gyrostabilized platform to a small constant input torque is analyzed in respect to the effect of the time delay (inherent or deliberately introduced) in the correction torque supplied by the servomotor, which itself may be non-linear to a certain extent. The equation of motion of the platform system is a third order nonlinear non-homogeneous differential equation. An approximate analytical method of solution of this equation is utilized. The value of the delay at which the platform response becomes unstable has been calculated by using this approximate analytical method. The procedure is illustrated by means of a numerical example. Second, the non-linear response of the platform to a random input has been obtained. The effects of several types of non-linearity on reducing the level of the mean square response have been investigated, by applying the technique of equivalent linearization and solving the resulting integral equations by using laguerre or Gaussian integration techniques. The mean square responses to white noise and band limited white noise, for various values of the non-linear parameter and for different types of non-linearity function, have been obtained. For positive values of the non-linear parameter the levels of the non-linear mean square responses to both white noise and band-limited white noise are low as compared to the linear mean square response. For negative values of the non-linear parameter the level of the non-linear mean square response at first increases slowly with increasing values of the non-linear parameter and then suddenly jumps to a high level, at a certain value of the non-linearity parameter.

A Proof of Convergence of the B-RED and P-RED Algorithms for Random Early Detection

In [8], we recently presented two computationally efficient algorithms named B-RED and P-RED for random early detection. In this letter, we present the mathematical proof of convergence of these algorithms under general conditions to local minima.