Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Given an unweighted undirected or directed graph with n vertices, m edges and edge connectivity c, we present a new deterministic algorithm for edge splitting. Our algorithm splits-off any specified subset S of vertices satisfying standard conditions (even degree for the undirected case and in-degree ≥ out-degree for the directed case) while maintaining connectivity c for vertices outside S in Õ(m+nc2) time for an undirected graph and Õ(mc) time for a directed graph. This improves the current best deterministic time bounds due to Gabow [8], who splits-off a single vertex in Õ(nc2+m) time for an undirected graph and Õ(mc) time for a directed graph. Further, for appropriate ranges of n, c, |S| it improves the current best randomized bounds due to Benczúr and Karger [2], who split-off a single vertex in an undirected graph in Õ(n2) Monte Carlo time. We give two applications of our edge splitting algorithms. Our first application is a sub-quadratic (in n) algorithm to construct Edmonds' arborescences. A classical result of Edmonds [5] shows that an unweighted directed graph with c edge-disjoint paths from any particular vertex r to every other vertex has exactly c edge-disjoint arborescences rooted at r. For a c edge connected unweighted undirected graph, the same theorem holds on the digraph obtained by replacing each undirected edge by two directed edges, one in each direction. The current fastest construction of these arborescences by Gabow [7] takes Õ(n2c2) time. Our algorithm takes Õ(nc3+m) time for the undirected case and Õ(nc4+mc) time for the directed case. The second application of our splitting algorithm is a new Steiner edge connectivity algorithm for undirected graphs which matches the best known bound of Õ(nc2 + m) time due to Bhalgat et al [3]. Finally, our algorithm can also be viewed as an alternative proof for existential edge splitting theorems due to Lovász [9] and Mader [11].

Origin of Disk Lopsidedness in Spiral Galaxies

In our work we have used the atomic hydrogen [HΙ] gas distribution in the HΙ 21-cm line emission to study the dark matter halo perturbations. For tHΙs analysis, the 2-D HΙ surface density and velocity maps (arcHΙval) of the galaxies in the Eridanus group (obtained using the GMRT) and in the Ursa Major group (obtained from WSRT) were used. In addition a few HΙckson Compact Groups of galaxies were also studied using the GMRT. The HΙ maps of these galaxies were Fourier analysed to estimate the asymmetry in the distribution and motion of gas. The average asymmetry parameter in the 1.5 to 2.5 K′-band scale lengths was found to be ~ 0.27 for the Eridanus group of galaxies wHΙle it was ~ 0.14 for the Ursa Major group of galaxies. The asymmetries in the distribution of HΙ as a function of Hubble type of galaxies were also studied and was found to be directly correlated with the compactness of the groups. In addition, the trend in the asymmetry as a function of the Hubble type of galaxies was opposite to that seen in the field galaxies, i.e., in the group galaxies, the early type galaxies showed more asymmetry than late type. These two aspects indicated that tidal interactions between the galaxies in a group environment to be the major cause of asymmetries. The observed asymmetry parameters were consistent with recent numerical simulations of asymmetries of gas disk caused by fly-by interactions. We have also estimated the perturbation of dark matter halo using the asymmetry parameter obtained from the Fourier series analysis of the surface density maps.

An O(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 Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ 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 running time of our algorithm for simple unweighted graphs is Õ(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 Õ(n20/9) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(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 ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

Boxicity of line graphs

The boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R(k). In this paper we show that for a line graph G of a multigraph, box(G) <= 2 Delta (G)(inverted right perpendicularlog(2) log(2) Delta(G)inverted left perpendicular + 3) + 1, where Delta(G) denotes the maximum degree of G. Since G is a line graph, Delta(G) <= 2(chi (G) - 1), where chi (G) denotes the chromatic number of G, and therefore, box(G) = 0(chi (G) log(2) log(2) (chi (G))). For the d-dimensional hypercube Q(d), we prove that box(Q(d)) >= 1/2 (inverted right perpendicularlog(2) log(2) dinverted left perpendicular + 1). The question of finding a nontrivial lower bound for box(Q(d)) was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795-5800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once). (C) 2011 Elsevier B.V. All rights reserved.

Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Variation of the gas and radiation content in the sub-Keplerian accretion disk around black holes and its impact to the solutions

We investigate the variation of the gas and the radiation pressure in accretion disks during the infall of matter to the black hole and its effect to the flow. While the flow far away from the black hole might be non-relativistic, in the vicinity of the black hole it is expected to be relativistic behaving more like radiation. Therefore, the ratio of gas pressure to total pressure (beta) and the underlying polytropic index (gamma) should not be constant throughout the flow. We obtain that accretion flows exhibit significant variation of beta and then gamma, which affects solutions described in the standard literature based on constant beta. Certain solutions for a particular set of initial parameters with a constant beta do not exist when the variation of beta is incorporated appropriately. We model the viscous sub-Keplerian accretion disk with a nonzero component of advection and pressure gradient around black holes by preserving the conservations of mass, momentum, energy, supplemented by the evolution of beta. By solving the set of five coupled differential equations, we obtain the thermo-hydrodynamical properties of the flow. We show that during infall, beta of the flow could vary up to similar to 300%, while gamma up to similar to 20%. This might have a significant impact to the disk solutions in explaining observed data, e.g. super-luminal jets from disks, luminosity, and then extracting fundamental properties from them. Hence any conclusion based on constant gamma and beta should be taken with caution and corrected. (C) 2011 Elsevier B.V. All rights reserved.

Acyclic edge coloring of 2-degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)<=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a'(G)<=Delta + 1. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68:1-27, 2011

Role of Nonplanar Peptide Unit in Regular Polypeptide Helices - New Model for Pply-Beta-Benzyl-L-Aspartate

The effect of non-planarity of the peptide unit on helical structures stabilized by intrachain hydrogen bonds is discussed. While the present calculations generally agree with those already reported in the literature for right-handed helical structures, it is found that the most stable left-handed structure is a novel helix, called the delta-helix. Its helical parameters are close to these reported for poly-beta-benzyl-L -aspartate. Conformational energy calculations show that poly-beta-benzyl-L -aspartate with the delta-helical structure is considerably more stable than the structure it is generally believed to take up (the omega-helix) by about 15 kcal/mol-residue.

Molecular Dynamics of Thermotropic Liquid Crystals: Anomalous relaxation dynamics of calamitic and discotic liquid crystals

Recent optical kerr effect (OKE) studies have demonstrated that orientational relaxation of rod-like nematogens exhibits temporal power law decay at intermediate times not only near the isotropic–nematic (I–N) phase boundary but also in the nematic phase. Such behaviour has drawn an intriguing analogy with supercooled liquids. We have investigated both collective and single-particle orientational dynamics of a family of model system of thermotropic liquid crystals using extensive computer simulations. Several remarkable features of glassy dynamics are on display including non-exponential relaxation, dynamical heterogeneity, and non-Arrhenius temperature dependence of the orientational relaxation time. Over a temperature range near the I–N phase boundary, the system behaves remarkably like a fragile glass-forming liquid. Using proper scaling, we construct the usual relaxation time versus inverse temperature plot and explicitly demonstrate that one can successfully define a density dependent fragility of liquid crystals. The fragility of liquid crystals shows a temperature and density dependence which is remarkably similar to the fragility of glass forming supercooled liquids. Energy landscape analysis of inherent structures shows that the breakdown of the Arrhenius temperature dependence of relaxation rate occurs at a temperature that marks the onset of the growth of the depth of the potential energy minima explored by the system. A model liquid crystal, consisting of disk-like molecules, has also been investigated in molecular dynamics simulations for orientational relaxation along two isobars starting from the high temperature isotropic phase. The isobars have been so chosen that the phase sequence isotropic (I)–nematic (N)–columnar (C) appears upon cooling along one of them and the sequence isotropic (I)–columnar(C) along the other. While the orientational relaxation in the isotropic phase near the I–N phase transition shows a power law decay at short to intermediate times, such power law relaxation is not observed in the isotropic phase near the I–C phase boundary. The origin of the power law decay in the single-particle second-rank orientational time correlation function (OTCF) is traced to the growth of the orientational pair distribution functions near the I–N phase boundary. As the system settles into the nematic phase, the decay of the single-particle second-rank orientational OTCF follows a pattern that is similar to what is observed with calamitic liquid crystals and supercooled molecular liquids.

Minor mergers and their impact on the kinematics of old and young stellar populations in disk galaxies

By means of N-body simulations we investigate the impact of minor mergers on the angular momentum and dynamical properties of the merger remnant. Our simulations cover a range of initial orbital characteristics and gas-to-stellar mass fractions (from 0 to 20%), and include star formation and supernova feedback. We confirm and extend previous results by showing that the specific angular momentum of the stellar component always decreases independently of the orbital parameters or morphology of the satellite, and that the decrease in the rotation velocity of the primary galaxy is accompanied by a change in the anisotropy of the orbits. However, the decrease affects only the old stellar population, and not the new population formed from gas during the merging process. This means that the merging process induces an increasing difference in the rotational support of the old and young stellar components, with the old one lagging with respect to the new. Even if our models are not intended specifically to reproduce the Milky Way and its accretion history, we find that, under certain conditions, the modeled rotational lag found is compatible with that observed in the Milky Way disk, thus indicating that minor mergers can be a viable way to produce it. The lag can increase with the vertical distance from the disk midplane, but only if the satellite is accreted along a direct orbit, and in all cases the main contribution to the lag comes from stars originally in the primary disk rather than from stars in the satellite galaxy. We also discuss the possibility of creating counter-rotating stars in the remnant disk, their fraction as a function of the vertical distance from the galaxy midplane, and the cumulative effect of multiple mergers on their creation.