90C27 Combinatorial optimization
Filtern
Erscheinungsjahr
- 2013 (1)
Dokumenttyp
- ZIB-Report (1)
Sprache
- Englisch (1)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1)
Schlagworte
- Steiner Connectivity Problem (1) (entfernen)
Institut
We extend the primal-dual approximation technique of Goemans and Williamson to the Steiner connectivity problem, a kind of Steiner tree problem in hypergraphs. This yields a (k+1)-approximation algorithm for the case that k is the minimum of the maximal number of nodes in a hyperedge minus 1 and the maximal number of terminal nodes in a hyperedge. These results require the proof of a degree property for terminal nodes in hypergraphs which generalizes the well-known graph property that the average degree of terminal nodes in Steiner trees is at most 2.