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.

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.

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.

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.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Varied Immune Response to FVIII: Presence of Proteolytic Antibodies Directed to Factor VIII in Different Human Pathologies

The versatility of antibodies is demonstrated by the various functions that they mediate such as neutralization, agglutination, fixation of the complement and its activation, and activation of effector cells. In addition to this plethora of functions, antibodies are capable of expressing enzymatic activity. Antibodies with catalytic function are a result of the productive interplay between the highly evolved machinery of the immune system and the chemical framework used to induce them (antigens). Catalytic antibodies are immunoglobulins with an ability to catalyze the reactions involving the antigen for which they are specific. Catalytic immunoglobulins of the IgM and IgG isotypes have been detected in the serum of healthy donors. In addition, catalytic immunoglobulins of the IgA isotype have been detected in the milk of healthy mothers. Conversely, antigen-specific hydrolytic antibodies have been reported in a number of inflammatory, autoimmune, and neoplastic disorders. The pathophysiological occurrence and relevance of catalytic antibodies remains a debated issue. Through the description of the hydrolysis of coagulation factor VIII as model target antigen, we propose that catalytic antibodies directed to the coagulation factor VIII may play a beneficial or a deleterious role depending on the immuno-inflammatory condition under which they occur.

Observation of Peierls transition in nanowires (diameter similar to 130 nm) of the charge transfer molecule TTF-TCNQ synthesized by electric-field-directed growth

We report the growth of nanowires of the charge transfer complex tetrathiafulvalene-tetracyanoquinodimethane (TTF-TCNQ) with diameters as low as 130 nm and show that such nanowires can show Peierls transitions at low temperatures. The wires of sub-micron length were grown between two prefabricated electrodes (with sub-micron gap) by vapor phase growth from a single source by applying an electric field between the electrodes during the growth process. The nanowires so grown show a charge transfer ratio similar to 0.57, which is close to that seen in bulk crystals. Below the transition the transport is strongly nonlinear and can be interpreted as originating from de-pinning of CDW that forms at the Peierls transition.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular 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, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Use of structure-directed DNA ligands to probe the binding of recA protein to narrow and wide grooves of DNA and on its ability to promote homologous pairing

We have used circular dichroism and structure-directed drugs to identify the role of structural features, wide and narrow grooves in particular, required for the cooperative polymerization, recognition of homologous sequences, and the formation of joint molecules promoted by recA protein. The path of cooperative polymerization of recA protein was deduced by its ability to cause quantitative displacement of distamycin from the narrow groove of duplex DNA. By contrast, methyl green bound to the wide groove was retained by the nucleoprotein filaments comprised of recA protein-DNA. Further, the mode of binding of these ligands and recA protein to DNA was confirmed by DNaseI digestion. More importantly, the formation of joint molecules was prevented by distamycin in the narrow groove while methyl green in the wide groove had no adverse effect. Intriguingly, distamycin interfered with the production of coaggregates between nucleoprotein filaments of recA protein-M13 ssDNA and naked linear M13 duplex DNA, but not with linear phi X174 duplex DNA. Thus, these data, in conjunction with molecular modeling, suggest that the narrow grooves of duplex DNA provide the fundamental framework required for the cooperative polymerization of recA protein and alignment of homologous sequences. These findings and their significance are discussed in relation to models of homologous pairing between two intertwined DNA molecules.

Acyclic edge coloring of subcubic 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 it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.

Anion directed template synthesis of Cu(II) complexes of a N,N,O donor mono-condensed Schiff base ligand: A molecular scaffold forming highly ordered H-bonded rectangular grids

Anion directed, template syntheses of two dinuclear copper(II) complexes of mono-condensed Schiff base ligand Hdipn (4-[(3-aminopentylimino)-methyl]-benzene-1,3-diol) involving 2,4- dihydroxybenzaldehyde and 1,3-diaminopentane were realized in the presence of bridging azide and acetate anions. Both complexes, [Cu-2(dipn)(2)(N-3)(2)] (1) and [Cu-2(dip(n))(2)(OAc)(2)] (2) have been characterized by X-ray crystallography. The two mononuclear units are joined together by basal-apical, double end-on azido bridges in complex 1 and by basal-apical, double mono-atomic acetate oxygen-bridges in 2. Both complexes form rectangular grid-like supramolecular structures via H-bonds connecting the azide or acetate anion and the p-hydroxy group of 2,4- dihydroxybenzaldehyde. Variable-temperature (300-2 K) magnetic susceptibility measurements reveal that complex 1 has antiferromagnetic coupling (J = -2.10 cm (1)) through the azide bridge while 2 has intra-dimer ferromagnetic coupling through the acetate bridge and inter-dimer antiferromagnetic coupling through H-bonds (J = 2.85 cm (1), J' = -1.08 cm (1)). (C) 2009 Elsevier B. V. All rights reserved.