Király, Tamás and Lau, Lap Chi (2006) Approximate minmax theorems of Steiner rootedorientations of hypergraphs. In: 47th Annual IEEE Symposium on Foundations of Computer Science. ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE . IEEE Computer Society, Los Alamitos, pp. 283292. ISBN 0769527205

Text
egres_06_13_u_141559.247129.pdf Download (410kB)  Preview 
Abstract
Given an undirected hypergraph and a subset of vertices S ⊆ V with a specified root vertex r ∈ S, the STEINER ROOTEDORIENTATION 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 minmax relations: • Given an undirected hypergraph H, if S is 2khyperedgeconnected in H, then H has a Steiner rooted khyperarcconnected orientation. • Given an undirected graph G, if S is 2kelementconnected in G, then G has a Steiner rooted kelementconnected 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. © 2006 IEEE.
Item Type:  Book Section 

Uncontrolled Keywords:  Theorem proving; Set theory; Problem solving; Graph theory; Computational complexity; Approximation algorithms; Undirected hypergraph; Steiner rootedorientation problem; GRAPHS; VERTICES 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  16 Dec 2014 13:35 
Last Modified:  16 Dec 2014 13:35 
URI:  http://real.mtak.hu/id/eprint/19503 
Actions (login required)
Edit Item 