An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

DOI10.1016/J.JDA.2015.10.003MaRDI QIDQ891823zbMATH OpenOpenAlexFDO

Authors Chia-Chen Wei, Sun-Yuan Hsieh, Chia-Wei Lee, Sheng-Lung Peng

Publication date 17 November 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2015.10.003

zbMATH Keywords

approximation algorithmsSteiner tree problempartial-terminal Steiner trees

Mathematics Subject Classification ID

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

Recommendations

• An Improved Approximation Ratio to the Partial-Terminal Steiner Tree Problem
• An improved algorithm for the Steiner tree problem with bounded edge-length
• On approximation algorithms for the terminal Steiner tree problem
• Approximation algorithms for the terminal Steiner tree problem
• Improved Approximations for the Steiner Tree Problem
• scientific article; zbMATH DE number 742979
• An improved approximation algorithm for the uniform cost-distance Steiner tree problem
• An improved LP-based approximation for Steiner tree

Cites work

• scientific article; zbMATH DE number 1305435 (Why is no real title available?)
• scientific article; zbMATH DE number 750011 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• A better constant-factor approximation for selected-internal Steiner minimum tree
• Algorithms for terminal Steiner trees
• An improved LP-based approximation for Steiner tree
• Approximating the selected-internal Steiner tree
• Computing and Combinatorics
• Faster exact algorithms for steiner trees in planar networks
• Improved Approximations for the Steiner Tree Problem
• On component-size bounded Steiner trees
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Reducibility among combinatorial problems
• The Complexity of Computing Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Steiner problem in phylogeny is NP-complete
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• The full Steiner tree problem
• The internal Steiner tree problem: Hardness and approximations
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(1)

• A new approach for the multiobjective minimum spanning tree

This page was built for publication: An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

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