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.

The key enzyme in galactose metabolism, UDP-galactose-4-epimerase, affects cell-wall integrity and morphology in Candida albicans even in the absence of galactose

The enzyme UDP-galactose-4-epimerase (GAL10) catalyzes a key step in galactose metabolism converting UDP-galactose to UDPglucose which then can get metabolized through glycolysis and TCA cycle thus allowing the cell to use galactose as a carbon and energy source. As in many fungi, a functional homolog of GAL10 exists in Candida albicans. The domainal organization of the homologs from Saccharomyces cerevisiae and C albicans show high degree of homology having both mutarotase and an epimerase domain. The former is responsible for the conversion of beta-D-galactose to alpha-D-galactose and the hitter for epimerization of UDP-galactose to UDP-glucose. Absence of C albicans GAL10 (CaGAL10) affects cell-wall organization, oxidative stress response, biofilm formation and filamentation. Cagal10 mutant cells tend to flocculate extensively as compared to the wild-type cells. The excessive filamentation in this mutant is reflected in its irregular and wrinkled colony morphology. Cagal10 strain is more susceptible to oxidative stress when tested in presence of H2O2. While the S. cerevsiae GAL10 (ScGAL10), essential for survival in the presence of galactose, has not been reported to have defects in the absence of galactose, the C albicans homolog shows these phenotypes during growth in the absence of galactose. Thus a functional CaGal10 is required not only for galactose metabolism but also for normal hyphal morphogenesis, colony morphology, maintenance of cell-wall integrity and for resistance to oxidative stress even in the absence of galactose. (c) 2006 Elsevier Inc. All rights reserved.

R3Mn1.5CuV0.5O9 (R = Y, Ho, Er, Tm, Yb and Lu) and Lu3Mn3-3xCu2xVxO9: New noncentro symmetric oxides related to YMnO3

We report formation of new noncentrosymmetric oxides of the formula, R3Mn1.5CuV0.5O9 for R = Y, Ho, Er, Tm, Yb and Lu, possessing the hexagonal RMnO3 (space group P6(3)cm) structure. These oxides could be regarded as the x = 0.5 members of a general series R3Mn3-3xCu2xVxO9. Investigation of the Lu-Mn-Cu-V-O system reveals the existence of isostructural solid solution series, Lu3Mn3-3xCu2xVxO9 for 0 < x <= 0.75. Magnetic and dielectric properties of the oxides are consistent with a random distribution of Mn3+, Cu2+ and V5+ atoms that preserve the noncentrosymmetric RMnO3 structure. (c) 2006 Elsevier Ltd. All rights reserved.

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.

A symmetric solution for a cylindrical shell enclosed in an elastic casing

The problem of a long, thin circular cylindrical shell enclosed in an elastic casing and subjected to a ring of radial load on the inner rim is solved using the Love function for the casing in conjunction with Flügge shell theory. Numerical work has been done with a digital computer and the results for stress and displacement fields are given for various values of the shell geometry parameters and material constants.

Compressible axially symmetric laminar boundary layer flow in the stagnation region of a blunt body in the presence of magnetic field

In this paper, the steady laminar viscous hypersonic flow of an electrically conducting fluid in the region of the stagnation point of an insulating blunt body in the presence of a radial magnetic field is studied by similarity solution approach, taking into account the variation of the product of density and viscosity across the boundary layer. The two coupled non-linear ordinary differential equations are solved simultaneously using Runge-Kutta-Gill method. It has been found that the effect of the variation of the product of density and viscosity on skin friction coefficient and Nusselt number is appreciable. The skin friction coefficient increases but Nusselt number decreases as the magnetic field or the total enthalpy at the wall increases

Limit analysis of rectangular R.C. slabs on ground

A method is presented for obtaining lower bound on the carrying capacity of reinforced concrete foundation slab-structures subject to non-uniform contact pressure distributions. Functional approach suggested by Vallance for simply supported square slabs subject to uniform pressure distribution has been extended to simply supported rectangular slabs subject to symmetrical non-uniform pressure distributions. Radial solutions, ideally suited for rotationally symmetric problems, are shown to be adoptable for regular polygonal slabs subject to contact pressure paraboloids with constant edge pressures. The functional approach has been shown to be well suited even when the pressure is varying along the edges.

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))).

Computing complete test graphs for hierarchical systems

Conformance testing focuses on checking whether an implementation. under test (IUT) behaves according to its specification. Typically, testers are interested it? performing targeted tests that exercise certain features of the IUT This intention is formalized as a test purpose. The tester needs a "strategy" to reach the goal specified by the test purpose. Also, for a particular test case, the strategy should tell the tester whether the IUT has passed, failed. or deviated front the test purpose. In [8] Jeron and Morel show how to compute, for a given finite state machine specification and a test purpose automaton, a complete test graph (CTG) which represents all test strategies. In this paper; we consider the case when the specification is a hierarchical state machine and show how to compute a hierarchical CTG which preserves the hierarchical structure of the specification. We also propose an algorithm for an online test oracle which avoids a space overhead associated with the CTG.

Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.