|
Published in:
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:
1. Given an undirected hypergraph H,
if S is 2k-hyperedge-connected in H,
then H has a Steiner rooted k-hyperarc-connected orientation.
2. Given an undirected graph G,
if S is 2k-element-connected in G,
then G has a Steiner rooted k-element-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.
Bibtex entry:
| AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s and Lau Chi, Lap}, |
| TITLE | = | {Approximate Min-Max Theorems for Steiner Rooted-Orientations of Graphs and Hypergraphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2006}, |
| NUMBER | = | {TR-2006-13} |