Premium
An approximation algorithm for the Steiner connectivity problem
Author(s) -
Borndörfer Ralf,
Karbstein Marika
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21809
Subject(s) - steiner tree problem , approximation algorithm , generalization , terminal (telecommunication) , mathematics , hypergraph , combinatorics , path (computing) , degree (music) , tree (set theory) , minimum spanning tree , computer science , discrete mathematics , computer network , mathematical analysis , physics , acoustics
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.