Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Hans Juergen Proemel; Angelika Steger 
Titel:
RNC-Approximation Algorithms for the Steiner Problem 
Abstract:
In this paper we present an RNC-algorithm for finding a minimum spanning tree in a weighted 3-uniform hypergraph, assuming the edge weights are given in unary, and a fully polynomial time randomized approximation scheme if the edge weights are given in binary. From this result we then derive RNC-approximation algorithms for the Steiner problem in networks with approximation ratio arbitrarily close to 5/3. 
Stichworte:
Steiner Trees; Minimum Spanning Trees; Networks; Hypergraphs; Approximation Algorithms; Randomized Algorithms; Parallel Algorithms 
Jahr:
1996 
Jahr / Monat:
1996-10-01 00:00:00 
Seiten/Umfang:
12