Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs

DOI10.1137/1.9781611974782.47zbMath1410.68285OpenAlexW4252659687MaRDI QIDQ4575785

Bundit Laekhanukit, Parinya Chalermsook, Daniel Vaz, Syamantak Das

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.47

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Bounded Degree Group Steiner Tree Problems ⋮ Unnamed Item ⋮ The minimum degree group Steiner problem