On the Cubicity of Interval Graphs

A k-cube (or ``a unit cube in k dimensions'') is defined as the Cartesian product R-1 x . . . x R-k where R-i (for 1 <= i <= k) is an interval of the form [a(i), a(i) + 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub(G), is defined as the minimum dimension k such that G has a k-cube representation. 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. We show that for any interval graph G with maximum degree Delta, cub(G) <= inverted right perpendicular log(2) Delta inverted left perpendicular + 4. This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity is equal to inverted right perpendicular log(2) Delta inverted left perpendicular.

Interval Data Classification under Partial Information: A Chance-Constraint Approach

This paper presents a Chance-constraint Programming approach for constructing maximum-margin classifiers which are robust to interval-valued uncertainty in training examples. The methodology ensures that uncertain examples are classified correctly with high probability by employing chance-constraints. The main contribution of the paper is to pose the resultant optimization problem as a Second Order Cone Program by using large deviation inequalities, due to Bernstein. Apart from support and mean of the uncertain examples these Bernstein based relaxations make no further assumptions on the underlying uncertainty. Classifiers built using the proposed approach are less conservative, yield higher margins and hence are expected to generalize better than existing methods. Experimental results on synthetic and real-world datasets show that the proposed classifiers are better equipped to handle interval-valued uncertainty than state-of-the-art.

Finite field computation technique for exact solution of systems of linear equations and interval linear programming problems

An error-free computational approach is employed for finding the integer solution to a system of linear equations, using finite-field arithmetic. This approach is also extended to find the optimum solution for linear inequalities such as those arising in interval linear programming probloms.

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

Epoch extraction from linear prediction residual for identification of closed glottis interval

In voiced speech analysis epochal information is useful in accurate estimation of pitch periods and the frequency response of the vocal tract system. Ideally, linear prediction (LP) residual should give impulses at epochs. However, there are often ambiguities in the direct use of LP residual since samples of either polarity occur around epochs. Further, since the digital inverse filter does not compensate the phase response of the vocal tract system exactly, there is an uncertainty in the estimated epoch position. In this paper we present an interpretation of LP residual by considering the effect of the following factors: 1) the shape of glottal pulses, 2) inaccurate estimation of formants and bandwidths, 3) phase angles of formants at the instants of excitation, and 4) zeros in the vocal tract system. A method for the unambiguous identification of epochs from LP residual is then presented. The accuracy of the method is tested by comparing the results with the epochs obtained from the estimated glottal pulse shapes for several vowel segments. The method is used to identify the closed glottis interval for the estimation of the true frequency response of the vocal tract system.

Nonlinear measures of QT interval series: novel indices of cardiac repolarization lability: MEDqthr and LLEqthr

In this study, we investigated nonlinear measures of chaos of QT interval time series in 28 normal control subjects, 36 patients with panic disorder and 18 patients with major depression in supine and standing postures. We obtained the minimum embedding dimension (MED) and the largest Lyapunov exponent (LLE) of instantaneous heart rate (HR) and QT interval series. MED quantifies the system's complexity and LLE predictability. There was a significantly lower MED and a significantly increased LLE of QT interval time series in patients. Most importantly, nonlinear indices of QT/HR time series, MEDqthr (MED of QT/HR) and LLEqthr (LLE of QT/HR), were highly significantly different between controls and both patient groups in either posture. Results remained the same even after adjusting for age. The increased LLE of QT interval time, series in patients with anxiety and depression is in line with our previous findings of higher QTvi (QT variability index, a log ratio of QT variability corrected for mean QT squared divided by heart rate variability corrected for mean heart rate squared) in these patients, using linear techniques. Increased LLEqthr (LLE of QT/HR) may be a more sensitive tool to study cardiac repolarization and a valuable addition to the time domain measures such as QTvi. This is especially important in light of the finding that LLEqthr correlated poorly and nonsignificantly with QTvi. These findings suggest an increase in relative cardiac sympathetic activity and a decrease in certain aspects of cardiac vagal function in patients with anxiety as well as depression. The lack of correlation between QTvi and LLEqthr suggests that this nonlinear index is a valuable addition to the linear measures. These findings may also help to explain the higher incidence of cardiovascular mortality in patients with anxiety and depressive disorders. (C) 2002 Elsevier Science Ireland Ltd. All rights reserved.

Possibility of chaos in interval friction experiments of martensites

Wuttig and Suzuki's model on anelastic nonlinearities in solids in the vicinity of martensite transformations is analysed numerically. This model shows chaos even in the absence of applied forcing field as a function of a temperature dependent parameter. Even though the model exhibits sustained oscillations as a function of the amplitude of the forcing term, it does not exactly capture the features of the experimental time series. We have improved the model by adding a symmetry breaking term. The improved model shows period doubling bifurcation as a function of the amplitude of the forcing term. The solutions of our improved model shows good resemblance with the nonsymmetric period four oscillation seen in the experiment. (C) 1999 Elsevier Science B.V. All rights reserved.

Nucleation-Growth Mode of Cubic-Tetragonal Transition with Coexistence of Phases over a Wide Temperature Interval in the High Temperature Ferroelectric Systems PbTiO3-BiMeO3:Me = Sc , and Zn1/2Ti1/2

Temperature dependent X-ray powder diffraction and dielectric studies have been carried out on tetragonal compositions of (1-x) PbTiO 3(x) BiMeO 3; Me similar to Sc and Zn 1/2 Ti 1/2. The cubic and the tetragonal phases coexist over more than 100 degrees C for 0.70 PbTiO 30.3 Bi ( Zn 1/2 Ti 1/2) O 3 and 0.66 PbTiO 30.34 BiScO 3. The wide temperature range of phase coexistence is shown to be an intrinsic feature of the system, and is attributed to the increase in the degree of the covalent character of the ( Pb +Bi ) O bond with increasing concentration of Bi at the Pb -site. The d-values of the {111} planes of the coexisting phases are nearly identical, suggesting this plane to be the invariant plane for the martensitic type cubic-tetragonal transformation occurring in these systems.

On existence of periodic solutions for stable interval plants with odd, sector type nonlinearities

In several systems, the physical parameters of the system vary over time or operating points. A popular way of representing such plants with structured or parametric uncertainties is by means of interval polynomials. However, ensuring the stability of such systems is a robust control problem. Fortunately, Kharitonov's theorem enables the analysis of such interval plants and also provides tools for design of robust controllers in such cases. The present paper considers one such case, where the interval plant is connected with a timeinvariant, static, odd, sector type nonlinearity in its feedback path. This paper provides necessary conditions for the existence of self sustaining periodic oscillations in such interval plants, and indicates a possible design algorithm to avoid such periodic solutions or limit cycles. The describing function technique is used to approximate the nonlinearity and subsequently arrive at the results. Furthermore, the value set approach, along with Mikhailov conditions, are resorted to in providing graphical techniques for the derivation of the conditions and subsequent design algorithm of the controller.

Statistical analysis of the position of the monsoon trough

Using surface charts at 0330GMT, the movement df the monsoon trough during the months June to September 1990 al two fixed longitudes, namely 79 degrees E and 85 degrees E, is studied. The probability distribution of trough position shows that the median, mean and mode occur at progressively more northern latitudes, especially at 85 degrees E, with a pronounced mode that is close to the northern-most limit reached by the trough. A spectral analysis of the fluctuating latitudinal position of the trough is carried out using FFT and the Maximum Entropy Method (MEM). Both methods show significant peaks around 7.5 and 2.6 days, and a less significant one around 40-50 days. The two peaks at the shorter period are more prominent at the eastern longitude. MEM shows an additional peak around 15 days. A study of the weather systems that occurred during the season shows them to have a duration around 3 days and an interval between systems of around 9 days, suggesting a possible correlation with the dominant short periods observed in the spectrum of trough position.

Structural correlations in GexSe1-x glasses - a neutron diffraction study

Neutron diffraction measurement is carried out on GexSe1-x glasses, where 0.1 less than or equal to x less than or equal to 0.4, in a Q interval of 0.55-13.8 Angstrom(-1). The first sharp diffraction peak (FSDP) in the structure factor, S(Q), shows a systematic increase in the intensity and shifts to a lower Q with increasing Ge concentration. The coherence length of FSDP increases with x and becomes maximum for 0.33 less than or equal to x less than or equal to 0.4. The Monte-Carlo method, due to Soper, is used to generate S(Q) and also the pair correlation function, g(r). The generated S(Q) is in agreement with the experimental data for all x. Analysis of the first four peaks in the total correlation function, T(r), shows that the short range order in GeSe2 glass is due to Ge(Se-1/2)(4) tetrahedra, in agreement with earlier reports. Se-rich glasses contain Se-chains which are cross-linked with Ge(Se-1/2)(4) tetrahedra. Ge-2(Se-1/2)(6) molecular units are the basic structural units in Ge-rich, x = 0.4, glass. For x = 0.2, 0.33 and 0.4 there is evidence for some of the tetrahedra being in an edge-shared configuration. The number of edge-shared tetrahedra in these glasses increase with increasing Ge content.

Non-linear regression model for spatial variation in precipitation chemistry for South India

Chemical composition of rainwater changes from sea to inland under the influence of several major factors - topographic location of area, its distance from sea, annual rainfall. A model is developed here to quantify the variation in precipitation chemistry under the influence of inland distance and rainfall amount. Various sites in India categorized as 'urban', 'suburban' and 'rural' have been considered for model development. pH, HCO3, NO3 and Mg do not change much from coast to inland while, SO4 and Ca change is subjected to local emissions. Cl and Na originate solely from sea salinity and are the chemistry parameters in the model. Non-linear multiple regressions performed for the various categories revealed that both rainfall amount and precipitation chemistry obeyed a power law reduction with distance from sea. Cl and Na decrease rapidly for the first 100 km distance from sea, then decrease marginally for the next 100 km, and later stabilize. Regression parameters estimated for different cases were found to be consistent (R-2 similar to 0.8). Variation in one of the parameters accounted for urbanization. Model was validated using data points from the southern peninsular region of the country. Estimates are found to be within 99.9% confidence interval. Finally, this relationship between the three parameters - rainfall amount, coastline distance, and concentration (in terms of Cl and Na) was validated with experiments conducted in a small experimental watershed in the south-west India. Chemistry estimated using the model was in good correlation with observed values with a relative error of similar to 5%. Monthly variation in the chemistry is predicted from a downscaling model and then compared with the observed data. Hence, the model developed for rain chemistry is useful in estimating the concentrations at different spatio-temporal scales and is especially applicable for south-west region of India. (C) 2008 Elsevier Ltd. All rights reserved.

A direct adaptive neural command controller design for an unstable helicopter

This paper presents an off-line (finite time interval) and on-line learning direct adaptive neural controller for an unstable helicopter. The neural controller is designed to track pitch rate command signal generated using the reference model. A helicopter having a soft inplane four-bladed hingeless main rotor and a four-bladed tail rotor with conventional mechanical controls is used for the simulation studies. For the simulation study, a linearized helicopter model at different straight and level flight conditions is considered. A neural network with a linear filter architecture trained using backpropagation through time is used to approximate the control law. The controller network parameters are adapted using updated rules Lyapunov synthesis. The off-line trained (for finite time interval) network provides the necessary stability and tracking performance. The on-line learning is used to adapt the network under varying flight conditions. The on-line learning ability is demonstrated through parameter uncertainties. The performance of the proposed direct adaptive neural controller (DANC) is compared with feedback error learning neural controller (FENC).