An approximation algorithm for the Steiner connectivity problem. Issue 2 (6th February 2018)

• Record Type: Journal Article
• Authors: Borndörfer, Ralf; Karbstein, Marika
• Is Part Of: Networks. Volume 72:Issue 2(2018)
• Page Start: 174
• Page End: 181
• Publication Date: 2018-02-06
• Subjects: degree property -- hypergraph -- primal‐dual approximation -- Steiner tree; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21809
• Languages: English
• ISSNs: 0028-3045

Abstract

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.