An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Transversely isotropic infinite cylindrical shell subjected to a radial axisymmetric line load

The problem of an infinite transversely isotropic circular cylindrical shell subjected to an axisymmetric radial external line load is investigated using elasticity theory, classical shell theory and shear deformation theory. The results obtained by these methods are compared for two ratios of inner to outer shell radius and for varying degrees of anisotropy. Some typical results are given here to show the effect of anisotropy and the thickness of the shell on the distribution of stresses and displacements.

Application of Haar functions for transmission line and transformer differential protection

The development of algorithms, based on Haar functions, for extracting the desired frequency components from transient power-system relaying signals is presented. The applications of these algorithms to impedance detection in transmission line protection and to harmonic restraint in transformer differential protection are discussed. For transmission line protection, three modes of application of the Haar algorithms are described: a full-cycle window algorithm, an approximate full-cycle window algorithm, and a half-cycle window algorithm. For power transformer differential protection, the combined second and fifth harmonic magnitude of the differential current is compared with that of fundamental to arrive at a trip decision. The proposed line protection algorithms are evaluated, under different fault conditions, using realistic relaying signals obtained from transient analysis conducted on a model 400 kV, 3-phase system. The transformer differential protection algorithms are also evaluated using a variety of simulated inrush and internal fault signals.

A necessary and sufficient condition for acyclic graphs

This letter gives a new necessary and sufficient condition to determine whether a directed graph is acyclic.

Improvement On Brooks Chromatic Bound For A Class Of Graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5−e and H) as an induced subgraph and if Δ(G)greater-or-equal, slanted6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)greater-or-equal, slanted6 can not be non-trivially relaxed and the graph K5−e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5−e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)greater-or-equal, slanted9 and d(G)<Δ(G), then χ(G)<Δ(G).

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.

On the number of two-line and three-line latin rectangles - an alternative approach

The number of two-line and three-line Latin rectangles is obtained by recursive methods in a setting slightly more general than usually considered. We show how this leads to a generalisation which is proved elsewhere.

Theoretical gain optimization studies in CO2-N2 lasers. III. Inclusion of line shape effects

The influence of Lorentz and Doppler line-broadening mechanisms on the small-signal optical gain of lasers and, in particular, gasdynamic lasers, is discussed. A relationship between the critical parameter reflecting the line-broadening mechanisms and some of the important parameters arising out of the gain optimization studies in CO2-N2 gasdynamic lasers is established. Using this relationship, methods by which the deleterious effect of the Doppler mechanisms on small-signal gain can be suppressed are suggested. Journal of Applied Physics is copyrighted by The American Institute of Physics.

Transversely isotropic infinite cylindrical shell subjected to a radial axisymmetric line load

The problem of an infinite transversely isotropic circular cylindrical shell subjected to an axisymmetric radial external line load is investigated using elasticity theory, classical shell theory and shear deformation theory. The results obtained by these methods are compared for two ratios of inner to outer shell radius and for varying degrees of anisotropy. Some typical results are given here to show the effect of anisotropy and the thickness of the shell on the distribution of stresses and displacements.

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.

AC conductivity of a quantum Hall line junction

We present a microscopic model for calculating the AC conductivity of a finite length line junction made up of two counter-or co-propagating single mode quantum Hall edges with possibly different filling fractions. The effect of density-density interactions and a local tunneling conductance (sigma) between the two edges is considered. Assuming that sigma is independent of the frequency omega, we derive expressions for the AC conductivity as a function of omega, the length of the line junction and other parameters of the system. We reproduce the results of Sen and Agarwal (2008 Phys. Rev. B 78 085430) in the DC limit (omega -> 0), and generalize those results for an interacting system. As a function of omega, the AC conductivity shows significant oscillations if sigma is small; the oscillations become less prominent as sigma increases. A renormalization group analysis shows that the system may be in a metallic or an insulating phase depending on the strength of the interactions. We discuss the experimental implications of this for the behavior of the AC conductivity at low temperatures.

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.

Line tension of a two dimensional gas-liquid interface

In two dimensional (2D) gas-liquid systems, the reported simulation values of line tension are known to disagree with the existing theoretical estimates. We find that while the simulation erred in truncating the range of the interaction potential, and as a result grossly underestimated the actual value, the earlier theoretical calculation was also limited by several approximations. When both the simulation and the theory are improved, we find that the estimate of line tension is in better agreement with each other. The small value of surface tension suggests increased influence of noncircular clusters in 2D gas-liquid nucleation, as indeed observed in a recent simulation.

Isotope shifts and hyperfine structure in the 555.8-nm S-1(0) -> P-3(1) line of Yb

We apply our technique of using a Rb-stabilized ring-cavity resonator to measure the frequencies of various spectral components in the 555.8-nm 1S0-->3P1 line of Yb. We determine the isotope shifts with 60 kHz precision, which is an order-of-magnitude improvement over the best previous measurement on this line. There are two overlapping transitions, 171Yb(1/2-->3/2) and 173Yb(5/2-->3/2), which we resolve by applying a magnetic field. We thus obtain the hyperfine constants in the 3P1 state of the odd isotopes with a significantly improved precision. Knowledge of isotope shifts and hyperfine structure should prove useful for high-precision calculations in Yb necessary to interpret ongoing experiments testing parity and time-reversal symmetry violation in the laws of physics.