Back to Search
Start Over
An approximation algorithm for the Steiner connectivity problem.
- Source :
- Networks; Sep2018, Vol. 72 Issue 2, p174-181, 8p
- Publication Year :
- 2018
-
Abstract
- This article presents an approximation algorithm for the Steiner connectivity problem, which is a generalization of the Steiner tree problem that involves paths instead of edges. The problem can also be seen as hypergraph‐version of the Steiner tree problem; it arises in line planning in public transport. We prove a k + 1 approximation guarantee, where k is the minimum of the maximum number of nodes in a path minus 1 and the maximum number of terminal nodes in a path. The result is based on a structural degree property for terminal nodes. [ABSTRACT FROM AUTHOR]
- Subjects :
- APPROXIMATION algorithms
STEINER systems
HYPERGRAPHS
Subjects
Details
- Language :
- English
- ISSN :
- 00283045
- Volume :
- 72
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Networks
- Publication Type :
- Academic Journal
- Accession number :
- 131437394
- Full Text :
- https://doi.org/10.1002/net.21809