A polylogarithmic approximation for computing non-metric terminal Steiner trees

DOI10.1016/j.ipl.2010.07.006zbMath1234.68464OpenAlexW2054665259MaRDI QIDQ407565

Danny Segev, Iftah Gamzu

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.07.006

zbMATH Keywords

approximation algorithmsgroup Steiner treeterminal Steiner tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• The full Steiner tree problem
• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• On the terminal Steiner tree problem.
• Algorithms for terminal Steiner trees
• An improved LP-based approximation for steiner tree
• On the Full and Bottleneck Full Steiner Tree Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A tight bound on approximating arbitrary metrics by tree metrics