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.

DNase I Site Mapping and Micrococcal Nuclease Digestion of Pachytene Chromatin Reveal Novel Structural Features

A comparison of the DNase I digestion products of the 32P-5’-end-labeled pachytene nucleosome core particles (containing histones H2A, TH2A, X2, H2B, THPB, H3a, nd H4) and liver nucleosome core particles (containing somatic histones H2A, H2B, H3, and H4) revealed that the cleavage sites that are 30, 40, and 110 nucleotidesa way from the 5’-enda re significantly more accessiblei n the pachytene core particles than in the liver core particles. These cleavage sites correspond to the region wherein H2B interacts with the nucleosome core DNA. These results, therefore, suggest that the histone-DNA interactiona t these sites in the pachytene core particles is weaker, possibly because of the presence of the histone variant THBB interacting at similar topological positions in the nucleosome core as that of its somatic counterpart H2B. Such a loosened structumrea y also be maintainede ven in the native pachytene chromatin since micrococcal nuclease digestion of pachytene nuclei resulted in a higher ratio of subnucleosomes (SN4 + SN?) to mononucleosomes than that observed liinv er chromatin

Comprehensive Path-sensitive Data-flow Analysis

Data-flow analysis is an integral part of any aggressive optimizing compiler. We propose a framework for improving the precision of data-flow analysis in the presence of complex control-flow. W initially perform data-flow analysis to determine those control-flow merges which cause the loss in data-flow analysis precision. The control-flow graph of the program is then restructured such that performing data-flow analysis on the resulting restructured graph gives more precise results. The proposed framework is both simple, involving the familiar notion of product automata, and also general, since it is applicable to any forward data-flow analysis. Apart from proving that our restructuring process is correct, we also show that restructuring is effective in that it necessarily leads to more optimization opportunities. Furthermore, the framework handles the trade-off between the increase in data-flow precision and the code size increase inherent in the restructuring. We show that determining an optimal restructuring is NP-hard, and propose and evaluate a greedy strategy. The framework has been implemented in the Scale research compiler, and instantiated for the specific problem of Constant Propagation. On the SPECINT 2000 benchmark suite we observe an average speedup of 4% in the running times over Wegman-Zadeck conditional constant propagation algorithm and 2% over a purely path profile guided approach.

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.

Distributed Scheduling for Multi-Hop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. We suggest how the greedy heuristic can be implemented in a distributed manner. We evaluate an analytical bound in detail, for the special case of a line graph and also provide a loose bound on the greedy heuristic for the case of an arbitrary graph.

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

Computer-aided analysis of the structure of kinematic chains

Using the link-link incidence matrix to represent a simple-jointed kinematic chain algebraic procedures have been developed to determine its structural characteristics such as the type of freedom of the chain, the number of distinct mechanisms and driving mechanisms that can be derived from the chain. A computer program incorporating these graph theory based procedures has been applied successfully for the structural analysis of several typical chains.

DFL: A Data Flow Language

Many novel computer architectures like array and multiprocessors which achieve high performance through the use of concurrency exploit variations of the von Neumann model of computation. The effective utilization of the machines makes special demands on programmers and their programming languages, such as the structuring of data into vectors or the partitioning of programs into concurrent processes. In comparison, the data flow model of computation demands only that the principle of structured programming be followed. A data flow program, often represented as a data flow graph, is a program that expresses a computation by indicating the data dependencies among operators. A data flow computer is a machine designed to take advantage of concurrency in data flow graphs by executing data independent operations in parallel. In this paper, we discuss the design of a high level language (DFL: Data Flow Language) suitable for data flow computers. Some sample procedures in DFL are presented. The implementation aspects have not been discussed in detail since there are no new problems encountered. The language DFL embodies the concepts of functional programming, but in appearance closely resembles Pascal. The language is a better vehicle than the data flow graph for expressing a parallel algorithm. The compiler has been implemented on a DEC 1090 system in Pascal.

Non-Abelian monopoles break color. I. Classical mechanics

Monopoles which are sources of non-Abelian magnetic flux are predicted by many models of grand unification. It has been argued elsewhere that a generic transformation of the "unbroken" symmetry group H cannot be globally implemented on such monopoles for reasons of topology. In this paper, we show that similar topological obstructions are encountered in the mechanics of a test particle in the field of these monopoles and that the transformations of H cannot all be globally implemented as canonical transformations. For the SU(5) model, if H is SU(3)C×U(1)em, a consequence is that color multiplets are not globally defined, while if H is SU(3)C×SU(2)WS×U(1)Y, the same is the case for both color and electroweak multiplets. There are, however, several subgroups KT, KT′,… of H which can be globally implemented, with the transformation laws of the observables differing from group to group in a novel way. For H=SU(3)C×U(1)em, a choice for KT is SU(2)C×U(1)em, while for H=SU(3)C×SU(2)WS×U(1)Y, a choice is SU(2)C×U(1)×U(1)×U(1). The paper also develops the differential geometry of monopoles in a form convenient for computations.

Non-Abelian monopoles break color. II. Field theory and quantum mechanics

Many grand unified theories (GUT's) predict non-Abelian monopoles which are sources of non-Abelian (and Abelian) magnetic flux. In the preceding paper, we discussed in detail the topological obstructions to the global implementation of the action of the "unbroken symmetry group" H on a classical test particle in the field of such a monopole. In this paper, the existence of similar topological obstructions to the definition of H action on the fields in such a monopole sector, as well as on the states of a quantum-mechanical test particle in the presence of such fields, are shown in detail. Some subgroups of H which can be globally realized as groups of automorphisms are identified. We also discuss the application of our analysis to the SU(5) GUT and show in particular that the non-Abelian monopoles of that theory break color and electroweak symmetries.

Classical solitons with no quantum counterparts and their supersymmetric revival

We demonstrate the phenomenon stated in the title, using for illustration a two-dimensional scalar-field model with a triple-well potential {fx837-1}. At the classical level, this system supports static topological solitons with finite energy. Upon quantisation, however, these solitons develop infinite energy, which cannot be renormalised away. Thus this quantised model has no soliton sector, even though classical solitons exist. Finally when the model is extended supersymmetrically by adding a Majorana field, finiteness of the soliton energy is recovered.

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.

ALWIN-Algorithmic Wiswesser Notation System for Organic Compounds

ALWIN, a new chemical notation system for organic compounds, based on the Wiswesser Line Notation, is described. Procedures and rules are given for constructing ALWIN for acyclic structures and cyclic structures, vi.?., benzene and Its derivatives, monocyclic, bicyclic, polycyclic, perifused, splro, bridged ring, and ring of rlngs systems. A new method called "tessellation" is introduced for the topological descrlptlon of fused and spiro ring systems. Also new concepts are introduced for describing bridged ring and ring of rlngs systems.

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.

Relaxation Time of Chemical Reactions from Network Thermodynamics

The relationship for the relaxation time(s) of a chemical reaction in terms of concentrations and rate constants has been derived from the network thermodynamic approach developed by Oster, Perelson, and Katchalsky.Generally, it is necessary to draw the bond graph and the “network analogue” of the reaction scheme, followed by loop or nodal analysis of the network and finally solving of the resulting differential equations. In the case of single-step reactions, however, it is possible to obtain an expression for the relaxation time. This approach is simpler and elegant and has certain advantages over the usual kinetic method. The method has been illustrated by taking different reaction schemes as examples.