A polylogarithmic approximation for computing non-metric terminal Steiner trees

DOI10.1016/J.IPL.2010.07.006zbMATH Open1234.68464OpenAlexW2054665259MaRDI QIDQ407565FDOQ407565

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

• 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
• An improved LP-based approximation for Steiner tree
• On approximation algorithms for the terminal Steiner tree problem
• On the terminal Steiner tree problem.
• On the Full and Bottleneck Full Steiner Tree Problems
• A note on the terminal Steiner tree problem
• Algorithms for terminal Steiner trees
• 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)