loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs
Berkeley, California
October 21-October 24
ISBN: 0-7695-2720-5
Tamas Kiraly, Eotvos Lorand University, Hungary
Lap Chi Lau, University of Toronto, Canada
Given an undirected hypergraph and a subset of vertices S \subseteq V with a specified root vertex r \in S, the STEINER ROOTED-ORIENTATION problem is to find an orientation of all the hyperedges so that in the resulting directed hypergraph the "connectivity" from the root r to the vertices in S is maximized. This is motivated by a multicasting problem in undirected networks as well as a generalization of some classical problems in graph theory. The main results of this paper are the following approximate min-max relations:

--Given an undirected hypergraph H, if S is 2khyperedge- connected in H, then H has a Steiner rooted k-hyperarc-connected orientation.

--Given an undirected graph G, if S is 2k-elementconnected in G, then G has a Steiner rooted kelement- connected orientation.

Both results are tight in terms of the connectivity bounds. These also give polynomial time constant factor approximation algorithms for both problems. The proofs are based on submodular techniques, and a graph decomposition technique used in the STEINER TREE PACKING problem. Some complementary hardness results are presented at the end.

Citation:
Tamas Kiraly, Lap Chi Lau, "Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs," focs, pp.283-292, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.