Login
- Document type:
- Technical Report
- Author(s):
- Hans Juergen Proemel; Angelika Steger
- Title:
- 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.
- Keywords:
- Steiner Trees; Minimum Spanning Trees; Networks; Hypergraphs; Approximation Algorithms; Randomized Algorithms; Parallel Algorithms
- Year:
- 1996
- Year / month:
- 1996-10-01 00:00:00
- Pages:
- 12
BibTeX