An approximation algorithm for the Steiner connectivity problem | Zendy

Borndörfer Ralf | Zendy; Karbstein Marika | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research