Home About us Contact
|
Home About us Contact | ||
|
|
||
Undirected Graph (undirected + graph)
Selected AbstractsA branch-and-cut algorithm for partition coloringNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2010Yuri Frota Abstract Let G = (V, E, Q) be a undirected graph, where V is the set of vertices, E is the set of edges, and Q = {Q1,,,Qq} is a partition of V into q subsets. We refer to Q1,,,Qq as the components of the partition. The partition coloring problem (PCP) consists of finding a subset V, of V with exactly one vertex from each component Q1,,,Qq and such that the chromatic number of the graph induced in G by V, is minimum. This problem is a generalization of the graph coloring problem. This work presents a branch-and-cut algorithm proposed for PCP. An integer programing formulation and valid inequalities are proposed. A tabu search heuristic is used for providing primal bounds. Computational experiments are reported for random graphs and for PCP instances originating from the problem of routing and wavelength assignment in all-optical WDM networks. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source] Packing the Steiner trees of a graphNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2009L. Petingi Abstract Let G = (V,E) be an undirected graph with a distinguished set of terminal vertices K , V, |K| , 2. A K -Steiner tree T of G is a tree containing the terminal vertex-set K, where any vertex of degree one in T must belong to K. The Steiner Tree Packing problem (STPP for short) is the problem of finding the maximum number of edge-disjoint K -Steiner trees, tK(G), contained in G. Specifically we are interested in finding a lower bound on tK(G) with respect to the K -edge-connectivity, denoted as ,K(G). In 2003, Kriesell conjectured that any graph G with terminal vertex-set K has at least ,,K(G)/2, edge-disjoint K -Steiner trees. In this article, we show that this conjecture can be answered affirmatively if the edges of G can be partitioned into K -Steiner trees. This result yields bounds for the problem of packing K -Steiner trees with certain intersection properties in a graph. In addition we show that for any graph G with terminal vertex-set K, tK(G) , ,,K(G)/2, , |V , K|/2 , 1. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source] Approximation algorithms for the k-source multicast tree construction problemNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2006Paraskevi Fragopoulou Abstract Given an undirected graph with nonnegative weights on its edges, a group of source nodes, and a group of destination nodes, we investigate the problem of constructing a multicast tree that minimizes the sum of distances from a destination node to all sources. This problem has been proven to be NP-complete. In this article, we show that there is a point c of the graph such that a shortest paths tree constructed from c is a 2-approximation to the problem, a significant improvement over the previous results, and we present an efficient approximation algorithm. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 178,183 2006 [source] All-port line broadcasting in highly connected graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2005Iris Gaber Abstract In this article we propose polynomial time broadcasting protocols for an undirected graph under the circuit switched all-port model. In this model one vertex initiates a message and must inform all vertices of the graph of the message. The message is passed between the vertices of the graph in a sequence of rounds, where during a round the vertices communicate along edge disjoint paths. Our algorithms will require the graph to have a certain edge connectivity lower bound, to achieve fast broadcasting time. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 95,103 2005 [source] Local search with perturbations for the prize-collecting Steiner tree problem in graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2001S. A. Canuto Abstract Given an undirected graph with prizes associated with its nodes and weights associated with its edges, the prize-collecting Steiner tree problem consists of finding a subtree of this graph which minimizes the sum of the weights of its edges plus the prizes of the nodes not spanned. In this paper, we describe a multistart local search algorithm for the prize-collecting Steiner tree problem, based on the generation of initial solutions by a primal-dual algorithm using perturbed node prizes. Path-relinking is used to improve the solutions found by local search and variable neighborhood search is used as a post-optimization procedure. Computational experiments involving different algorithm variants are reported. Our results show that the local search with perturbations approach found optimal solutions on nearly all of the instances tested. © 2001 John Wiley & Sons, Inc. [source] Chain graph models and their causal interpretations,JOURNAL OF THE ROYAL STATISTICAL SOCIETY: SERIES B (STATISTICAL METHODOLOGY), Issue 3 2002Steffen L. Lauritzen Chain graphs are a natural generalization of directed acyclic graphs and undirected graphs. However, the apparent simplicity of chain graphs belies the subtlety of the conditional independence hypotheses that they represent. There are many simple and apparently plausible, but ultimately fallacious, interpretations of chain graphs that are often invoked, implicitly or explicitly. These interpretations also lead to flawed methods for applying background knowledge to model selection. We present a valid interpretation by showing how the distribution corresponding to a chain graph may be generated from the equilibrium distributions of dynamic models with feed-back. These dynamic interpretations lead to a simple theory of intervention, extending the theory developed for directed acyclic graphs. Finally, we contrast chain graph models under this interpretation with simultaneous equation models which have traditionally been used to model feed-back in econometrics. [source] Approximating the smallest k -edge connected spanning subgraph by LP-roundingNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009Harold 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 propertiesRANDOM STRUCTURES AND ALGORITHMS, Issue 4 2010Tim 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] | ||||||||||