Home About us Contact
|
Home About us Contact | ||
|
|
||
Digraph D (digraph + d)
Selected AbstractsSolution of a conjecture of Tewes and Volkmann regarding extendable cycles in in-tournamentsJOURNAL OF GRAPH THEORY, Issue 1 2010Dirk Meierling Abstract A directed cycle C of a digraph D is extendable if there exists a directed cycle C, in D that contains all vertices of C and an additional one. In 1989, Hendry defined a digraph D to be cycle extendable if it contains a directed cycle and every non-Hamiltonian directed cycle of D is extendable. Furthermore, D is fully cycle extendable if it is cycle extendable and every vertex of D belongs to a directed cycle of length three. In 2001, Tewes and Volkmann extended these definitions in considering only directed cycles whose length exceed a certain bound 3,k On Vertices of outdegree n in minimally n -connected digraphsJOURNAL OF GRAPH THEORY, Issue 2 2002W. Mader Abstract Let |D| and |D|+n denote the number of vertices of D and the number of vertices of outdegree n in the digraph D, respectively. It is proved that every minimally n -connected, finite digraph D has |D|+n,,,n,+,1 and that for n,,,2, there is a cn,>,0 such that for all minimally n -connected, finite digraphs D. Furthermore, case n,=,2 of the following conjecture is settled which says that every minimally n -connected, finite digraph has a vertex of indegree and outdegree equal to n. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 129,144, 2002 [source] Approximability of unsplittable shortest path routing problems,NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2009Andreas Bley Abstract In this article, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph D = (V,A) and a set K of directed commodities, an USPR is a set of flow paths P, (s,t) , K, such that there exists a metric , = (,a) , Z with respect to which each P is the unique shortest (s,t)-path. In the Min-Con-USPR problem, we seek an USPR that minimizes the maximum congestion over all arcs. We show that this problem is NP-hard to approximate within a factor of O(|V|1,,), but polynomially approximable within min(|A|,|K|) in general and within O(1) if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of ,(|V|2) larger than that achievable by unsplittable flow routing or by shortest multipath routing, and a factor of ,(|V|) larger than that achievable by unsplittable source-invariant routing. In the CAP -USPR problem, we seek a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is NP-hard to approximate within 2 , , even in the undirected case, and we devise approximation algorithms for various special cases. The fixed charge network design problem FC-USPR, where the task is to find a minimum cost subgraph of D whose fixed arc capacities admit an USPR of the commodities, is shown to be NPO-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source] Transversals of subtree hypergraphs and the source location problem in digraphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2008Jan van den Heuvel Abstract A hypergraph H = (V,E) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T. Since the number of edges of a subtree hypergraph can be exponential in n = |V|, one can not always expect to be able to find a minimum size transversal in time polynomial in n. In this paper, we show that if it is possible to decide if a set of vertices W , V is a transversal in time S(n) (where n = |V|), then it is possible to find a minimum size transversal in O(n3S(n)). This result provides a polynomial algorithm for the Source Location Problem: a set of (k,l)-sources for a digraph D = (V,A) is a subset S of V such that for any v , V there are k arc-disjoint paths that each join a vertex of S to v and l arc-disjoint paths that each join v to S. The Source Location Problem is to find a minimum size set of (k,l)-sources. We show that this is a case of finding a transversal of a subtree hypergraph, and that in this case S(n) is polynomial. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source] The strongly connected reliability of complete digraphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2005J.I. Brown Abstract Given a digraph D, consider the model where each vertex is always operational, but the edges are independently operational with probability p. The strongly connected reliability of D, scRel(D,p), is the probability that the spanning subgraph of D consisting of the operational edges is strongly connected. One can view strongly connected reliability as the probability that any vertex can send information to any other vertex, given that edges fail independently. There are very few classes for which there is an efficient algorithm for calculating the strongly connected reliability. This article presents the fist polynomial time algorithm for computing the strongly connected reliability of complete digraphs, that is, digraphs in which every vertex is joined to every other vertex by exactly one edge (one in each direction). © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 165,168 2005 [source]
| | |||||||||