			Home About us Contact

Directed Graph (directed + graph)

Distribution by Scientific Domains

Mathematics and Statistics	58%

Selected Abstracts

An improved direct labeling method for the max,flow min,cut computation in large hypergraphs and applications

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2003
Joachim Pistorius
Algorithms described so far to solve the maximum flow problem on hypergraphs first necessitate the transformation of these hypergraphs into directed graphs. The resulting maximum flow problem is then solved by standard algorithms. This paper describes a new method that solves the maximum flow problem directly on hypergraphs, leading to both reduced run time and lower memory requirements. We compare our approach with a state,of,the,art algorithm that uses a transformation of the hypergraph into a directed graph and an augmenting path algorithm to compute the maximum flow on this directed graph: the run,time complexity as well as the memory space complexity are reduced by a constant factor. Experimental results on large hypergraphs from VLSI applications show that the run time is reduced, on average, by a factor approximately 2, while memory occupation is reduced, on average, by a factor of 10. This improvement is particularly interesting for very large instances, to be solved in practical applications. [source]

Algorithms for the Weight Constrained Shortest Path Problem

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2001
Irina Dumitrescu
Given a directed graph whose arcs have an associated cost, and associated weight, the weight constrained shortest path problem (WCSPP) consists of finding a least-cost path between two specified nodes, such that the total weight along the path is less than a specified value. We will consider the case of the WCSPP defined on a graph without cycles. Even in this case, the problem is NP-hard, unless all weights are equal or all costs are equal, however pseudopolynomial time algorithms are known. The WCSPP applies to a number of real-world problems. Traditionally, dynamic programming approaches were most commonly used, but in recent times other methods have been developed, including exact approaches based on Lagrangean relaxation, and fully polynomial approximation schemes. We will review the area and present a new exact algorithm, based on scaling and rounding of weights. [source]

Graph-theoretical identification of dissociation pathways on free energy landscapes of biomolecular interaction

JOURNAL OF COMPUTATIONAL CHEMISTRY, Issue 4 2010
Ling Wang
Abstract Biomolecular association and dissociation reactions take place on complicated interaction free energy landscapes that are still very hard to characterize computationally. For large enough distances, though, it often suffices to consider the six relative translational and rotational degrees of freedom of the two particles treated as rigid bodies. Here, we computed the six-dimensional free energy surface of a dimer of water-soluble alpha-helices by scanning these six degrees of freedom in about one million grid points. In each point, the relative free energy difference was computed as the sum of the polar and nonpolar solvation free energies of the helix dimer and of the intermolecular coulombic interaction energy. The Dijkstra graph algorithm was then applied to search for the lowest cost dissociation pathways based on a weighted, directed graph, where the vertices represent the grid points, the edges connect the grid points and their neighbors, and the weights are the reaction costs between adjacent pairs of grid points. As an example, the configuration of the bound state was chosen as the source node, and the eight corners of the translational cube were chosen as the destination nodes. With the strong electrostatic interaction of the two helices giving rise to a clearly funnel-shaped energy landscape, the eight lowest-energy cost pathways coming from different orientations converge into a well-defined pathway for association. We believe that the methodology presented here will prove useful for identifying low-energy association and dissociation pathways in future studies of complicated free energy landscapes for biomolecular interaction. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2010 [source]

Conservation laws for Lotka,Volterra models

MATHEMATICAL METHODS IN THE APPLIED SCIENCES, Issue 17 2003
Rainer Schimming
Abstract We derive necessary and sufficient conditions on a Lotka,Volterra model to admit a conservation law of Volterra's type. The result and the proof for the corresponding linear algebra problem are given in graph-theoretical terms; they refer to the directed graph which is defined by the coefficients of the differential equation system. Copyright © 2003 John Wiley & Sons, Ltd. [source]

On the cycle polytope of a directed graph and its relaxations,

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2009
Egon Balas
Abstract We continue the investigation of the cycle polytope of a digraph begun by Balas and Oosten (Networks 36 (2000), 34,46) and derive a rich family of facets that cut off the origin and are not related to facets of the traveling salesman polytope. This disproves a claim in (Balas and Oosten 36 (2000), 34,46) that the only such facets are those defined by the linear ordering inequalities. After examining the relationship between the cycle polytope, its dominant, and the upper cycle polyhedron, we turn to the polar relationship between cycles and permutations or transitive tournaments. Our central result is a characterization of the relationship between facets of the dominant of the cycle polytope, facets of the cycle polytope that cut off the origin, and vertices of the linear relaxation of the transitive tournament polytope. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

Models and heuristics for a minimum arborescence problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2008
Christophe Duhamel
Abstract The Minimum Arborescence problem (MAP) consists of finding a minimum cost arborescence in a directed graph. This problem is NP-Hard and is a generalization of two well-known problems: the Minimum Spanning Arborescence Problem (MSAP) and the Directed Node Weighted Steiner Tree Problem (DNWSTP). We start the model presentation in this paper by describing four models for the MSAP (including two new ones, using so called "connectivity" constraints which forbid disconnected components) and we then describe the changes induced on the polyhedral structure of the problem by the removal of the spanning property. Only two (the two new ones) of the four models for the MSAP remain valid when the spanning property is removed. We also describe a multicommodity flow reformulation for the MAP that differs from well-known multicommodity flow reformulations in the sense that the flow conservation constraints at source and destination are replaced by inequalities. We show that the linear programming relaxation of this formulation is equivalent to the linear programming relaxation of the best of the two previous valid formulations and we also propose two Lagrangean relaxations based on the multicommodity flow reformulation. From the upper bound perspective, we describe a constructive heuristic as well as a local search procedure involving the concept of key path developed earlier for the Steiner Tree Problem. Numerical experiments taken from instances with up to 400 nodes are used to evaluate the proposed methods. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source]

Approximation algorithms for finding low-degree subgraphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2004
Philip N. Klein
Abstract We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by "proper" functions, a class of 0,1 functions indicating the number of edges crossing each cut. We also provide quasipolynomial-time approximation algorithms for finding two-edge-connected spanning subgraphs of approximately minimum degree of a given two-edge-connected graph, and a spanning tree (branching) of approximately minimum degree of a directed graph. The degree of the output network in all cases is guaranteed to be at most (1 + ,) times the optimal degree, plus an additive O(log1+,n) for any , > 0. Our analysis indicates that the degree of an optimal subgraph for each of the problems above is well estimated by certain polynomially solvable linear programs. This suggests that the linear programs we describe could be useful in obtaining optimal solutions via branch and bound. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 203,215 2004 [source]

The simple random walk and max-degree walk on a directed graph

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2009
Ravi Montenegro
Abstract We bound total variation and L, mixing times, spectral gap and magnitudes of the complex valued eigenvalues of general (nonreversible nonlazy) Markov chains with a minor expansion property. The resulting bounds for the (nonlazy) simple and max-degree walks on a (directed) graph are of the optimal order. It follows that, within a factor of two or four, the worst case of each of these mixing time and eigenvalue quantities is a walk on a cycle with clockwise drift. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

On the maximum number of Hamiltonian paths in tournaments

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2001
Ilan Adler
By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e,o(1)) (n!/2n,1). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 291,296, 2001 [source]

Complexity of resilient network optimisation,

EUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS, Issue 7 2009
Mateusz, otkiewicz
Path restoration (PR) is one of the basic mechanisms for securing telecommunication networks against failures. In the paper, we discuss the complexity of certain variants of a multi-commodity flow network optimisation problem in directed graphs related to state-independent path restoration mechanisms. We demonstrate that most variants of the considered problem are -hard. Depending on the variant, we show how the problem can be reduced either from the partition problem or from the problem of finding an arc-disjoint pair of paths that connect two distinct pairs of nodes. We also demonstrate that at the same time the considered problem is difficult to approximate. The complexity results of the paper are important as they can help to devise proper algorithms for resilient network design tools. Copyright © 2009 John Wiley & Sons, Ltd. [source]

An algorithm of propagation in weighted directed graphs with applications to economics and finance

INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS, Issue 3 2010
Mario Eboli
This paper puts forward an algorithm that computes the diffusion of events and actions across networks of economic agents, an algorithm that is applicable when such networks can be represented as weighted directed graphs. The functioning of the algorithm is shown in three applications. First, the algorithm is applied to a model of diffusion of innovation driven by the agents' imitation of their neighbors' behavior. Second, a graph-theoretic model of financial networks is introduced, and the corresponding algorithm is used to compute the so called domino effect, i.e., the diffusion of losses and insolvencies caused by the initial default of one or more agents. Finally, the algorithm is applied to the transfer of deposits operated by interbank liquidity networks. © 2010 Wiley Periodicals, Inc. [source]

An improved direct labeling method for the max,flow min,cut computation in large hypergraphs and applications

Bayesian analysis of directed graphs data with applications to social networks

JOURNAL OF THE ROYAL STATISTICAL SOCIETY: SERIES C (APPLIED STATISTICS), Issue 2 2004
Paramjit S. Gill
Summary., A fully Bayesian analysis of directed graphs, with particular emphasis on applica- tions in social networks, is explored. The model is capable of incorporating the effects of covariates, within and between block ties and multiple responses. Inference is straightforward by using software that is based on Markov chain Monte Carlo methods. Examples are provided which highlight the variety of data sets that can be entertained and the ease with which they can be analysed. [source]

Approximating the smallest k -edge connected spanning subgraph by LP-rounding

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009
Harold N. Gabow
Abstract The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k -edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. On the hardness side we show that for some absolute constant c > 0, for any integer k , 2 (k , 1), a polynomial-time algorithm approximating the smallest k -ECSS on undirected (directed) multigraphs to within ratio 1 + c/k would imply P = NP. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009 [source]

Testability and repair of hereditary hypergraph properties

RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2010
Tim Austin
Abstract Recent works of Alon,Shapira (A characterization of the (natural) graph properties testable with one-sided error. Available at: http://www.math.tau.ac.il/,nogaa/PDFS/heredit2.pdf) and Rödl,Schacht (Generalizations of the removal lemma, Available at: http://www.informatik.hu-berlin.de/,schacht/pub/preprints/gen_removal.pdf) have demonstrated that every hereditary property of undirected graphs or hypergraphs is testable with one-sided error; informally, this means that if a graph or hypergraph satisfies that property "locally" with sufficiently high probability, then it can be perturbed (or "repaired") into a graph or hypergraph which satisfies that property "globally." In this paper we make some refinements to these results, some of which may be surprising. In the positive direction, we strengthen the results to cover hereditary properties of multiple directed polychromatic graphs and hypergraphs. In the case of undirected graphs, we extend the result to continuous graphs on probability spaces and show that the repair algorithm is "local" in the sense that it only depends on a bounded amount of data; in particular, the graph can be repaired in a time linear in the number of edges. We also show that local repairability also holds for monotone or partite hypergraph properties (this latter result is also implicitly in (Ishigamis work Removal lemma for infinitely-many forbidden hypergraphs and property testing. Available at: arXiv.org: math.CO/0612669)). In the negative direction, we show that local repairability breaks down for directed graphs or for undirected 3-uniform hypergraphs. The reason for this contrast in behavior stems from (the limitations of) Ramsey theory. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [source]

Random dense bipartite graphs and directed graphs with specified degrees

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009
Catherine Greenhill
Abstract Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t. In particular, we find precise formulae for the probabilities that a given bipartite graph is edge-disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out-degrees s and in-degrees t. In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]