On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Random existence of charge ordered stripes and its influence on the magnetotransport properties of La0.6Sr0.4MnO3 perovskite substituted with diamagnetic ions at Mn sublattice

Phase-singular solid solutions of La0.6Sr0.4Mn1-yMeyO3 (0 <= y <= 0.3) [Me=Li1+, Mg2+, Al3+, Ti4+, Nb5+, Mo6+ or W6+] [LSMey] perovskite of rhombohedral symmetry (space group: R (3) over barc) have been prepared wherein the valence of the diamagnetic substituent at Mn site ranged from 1 to 6. With increasing y-content in LSMey, the metal-insulator (TM-I) transition in resistivity-temperature rho(T) curves shifted to low temperatures. The magnetization studies M(H) as well as the M(T) indicated two groups for LSMey. (1) Group A with Me=Mg, Al, Ti, or Nb which are paramagnetic insulators (PIs) at room temperature with low values of M (< 0.5 mu(B)/Mn); the magnetic transition [ferromagnetic insulator (FMI)-PI] temperature (T-C) shifts to low temperatures and nearly coincides with that of TM-I and the maximum magnetoresistance (MR) of similar to 50% prevails near T-C (approximate to TM-I). (2) Group-B samples with Me=Li, Mo, or W which are FMIs with M-s=3.3-3.58 mu(B)/Mn and marginal reduction in T-C similar to 350 K as compared to the undoped LSMO (T-C similar to 378 K). The latter samples show large temperature differences Delta T=T-c-TM-I, reaching up to similar to 288 K. The maximum MR (similar to 60%) prevails at low temperatures corresponding to the M-I transition TM-I rather than around T-C. High resolution lattice images as well as microscopy analysis revealed the prevalence of inhomogeneous phase mixtures of randomly distributed charge ordered-insulating (COI) bistripes (similar to 3-5 nm width) within FMI charge-disordered regions, yet maintaining crystallographically single phase with no secondary precipitate formation. The averaged ionic radius < r(B)>, valency, or charge/radius ratio < CRR > cannot be correlated with that of large Delta T; hence cannot be used to parametrize the discrepancy between T-C and TM-I. The M-I transition is controlled by the charge conduction within the electronically heterogeneous mixtures (COI bistripes+FMI charge disordered); large MR at TM-I suggests that the spin-ordered FM-insulating regions assist the charge transport, whereas the T-C is associated with the bulk spin ordered regions corresponding to the FMI phase of higher volume fraction of which anchors the T-C to higher temperatures. The present analysis showed that the double-exchange model alone cannot account for the wide bifurcation of the magnetic and electric transitions, contributions from the charge as well as lattice degrees of freedom to be separated from spin/orbital ordering. The heterogeneous phase mixtures (COI+FMI) cannot be treated as of granular composite behavior. (c) 2008 American Institute of Physics.

Topological properties of the one dimensional exponential random geometric graph

In this article we study the one-dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008.

Optimal multicommodity flow through the complete graph with random edge capacities

We consider a multicommodity flow problem on a complete graph whose edges have random, independent, and identically distributed capacities. We show that, as the number of nodes tends to infinity, the maximumutility, given by the average of a concave function of each commodity How, has an almost-sure limit. Furthermore, the asymptotically optimal flow uses only direct and two-hop paths, and can be obtained in a distributed manner.

Stability of scheduled multi-access communication over quasi-static flat fading channels with random coding and independent decoding

The stability of scheduled multiaccess communication with random coding and independent decoding of messages is investigated. The number of messages that may be scheduled for simultaneous transmission is limited to a given maximum value, and the channels from transmitters to receiver are quasistatic, flat, and have independent fades. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, we show the following: (1) in the limit of large message alphabet size, the stability region has an interference limited information-theoretic capacity interpretation, (2) state-independent scheduling policies achieve this asymptotic stability region, and (3) in the asymptotic limit corresponding to immediate access, the stability region for non-idling scheduling policies is shown to be identical irrespective of received signal powers.

Boxicity and cubicity of asteroidal triple free graphs

The boxicity of a graph G, denoted box(G), is the least integer d such that G is the intersection graph of a family of d-dimensional (axis-parallel) boxes. The cubicity, denoted cub(G), is the least dsuch that G is the intersection graph of a family of d-dimensional unit cubes. An independent set of three vertices is an asteroidal triple if any two are joined by a path avoiding the neighbourhood of the third. A graph is asteroidal triple free (AT-free) if it has no asteroidal triple. The claw number psi(G) is the number of edges in the largest star that is an induced subgraph of G. For an AT-free graph G with chromatic number chi(G) and claw number psi(G), we show that box(G) <= chi(C) and that this bound is sharp. We also show that cub(G) <= box(G)([log(2) psi(G)] + 2) <= chi(G)([log(2) psi(G)] + 2). If G is an AT-free graph having girth at least 5, then box(G) <= 2, and therefore cub(G) <= 2 [log(2) psi(G)] + 4. (c) 2010 Elsevier B.V. All rights reserved.

Detection of a periodic structure hidden in random background: the role of signal amplitude in the matched filter detection method

The matched filter method for detecting a periodic structure on a surface hidden behind randomness is known to detect up to (r(0)/Lambda) gt;= 0.11, where r(0) is the coherence length of light on scattering from the rough part and 3 is the wavelength of the periodic part of the surface-the above limit being much lower than what is allowed by conventional detection methods. The primary goal of this technique is the detection and characterization of the periodic structure hidden behind randomness without the use of any complicated experimental or computational procedures. This paper examines this detection procedure for various values of the amplitude a of the periodic part beginning from a = 0 to small finite values of a. We thus address the importance of the following quantities: `(a)lambda) `, which scales the amplitude of the periodic part with the wavelength of light, and (r(0))Lambda),in determining the detectability of the intensity peaks.

An instantaneous pulse frequency meter for random pulses

Counting-rate meters normally used for finding pulse frequencies are sluggish in their response to any rapid change in the pulse repetition frequency (P.R.F.). An instrument is described which measures each pulse interval and provides immediately afterwards an output voltage proportional to the reciprocal of interval duration. A response to a change in the P.R.F. as rapidly as is physically possible is obtained. The instrument has wide application in low level radiation detection and in several other fields especially for rapidly varying counting-rates.

First passage probability during random vibration

The probability that a random process crosses an arbitrary level for the first time is expressed as a Gram—Charlier series, the leading term of which is the Poisson approximation. The coefficients of this series are related to the moments of the number of level crossings. The results are applicable to both stationary and non-stationary processes. Some numerical results are presented for the response process of a linear single-degree-of-freedom oscillator under Gaussian white noise excitation.

Nonlinear vibration analysis of composite laminated and sandwich plates with random material properties

Nonlinear vibration analysis is performed using a C-0 assumed strain interpolated finite element plate model based on Reddy's third order theory. An earlier model is modified to include the effect of transverse shear variation along the plate thickness and Von-Karman nonlinear strain terms. Monte Carlo Simulation with Latin Hypercube Sampling technique is used to obtain the variance of linear and nonlinear natural frequencies of the plate due to randomness in its material properties. Numerical results are obtained for composite plates with different aspect ratio, stacking sequence and oscillation amplitude ratio. The numerical results are validated with the available literature. It is found that the nonlinear frequencies show increasing non-Gaussian probability density function with increasing amplitude of vibration and show dual peaks at high amplitude ratios. This chaotic nature of the dispersion of nonlinear eigenvalues is also r

A new class of separators and planarity of chordal graphs

We introduce a new class of clique separators, called base sets, for chordal graphs. Base sets of a chordal graph closely reflect its structure. We show that the notion of base sets leads to structural characterizations of planar k-trees and planar chordal graphs. Using these characterizations, we develop linear time algorithms for recognizing planar k-trees and planar chordal graphs. These algorithms are extensions of the Lexicographic_Breadth_First_Search algorithm for recognizing chordal graphs and are much simpler than the general planarity checking algorithm. Further, we use the notion of base sets to prove the equivalence of hamiltonian 2-trees and maximal outerplanar graphs.

On the complexity of finding stopping set size in Tanner Graphs

The problem of determining whether a Tanner graph for a linear block code has a stopping set of a given size is shown to be NT-complete.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).