A polylogarithmic approximation for computing non-metric terminal Steiner trees

DOI10.1016/J.IPL.2010.07.006MaRDI QIDQ407565zbMATH OpenOpenAlexFDO

Authors Iftah Gamzu, Danny Segev

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)

Recommendations

• On approximation algorithms for the terminal Steiner tree problem
• On the terminal Steiner tree problem.
• Computing and Combinatorics
• Algorithms for terminal Steiner trees
• New approximation algorithms for the Steiner tree problems

Cites work

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

Cited in

(1)

• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

This page was built for publication: A polylogarithmic approximation for computing non-metric terminal Steiner trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407565)