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

DOI10.1016/j.jda.2015.10.003zbMath1343.68317OpenAlexW2194722907MaRDI QIDQ891823

Sun-Yuan Hsieh, Chia-Chen Wei, 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

Steiner tree problemapproximation algorithmspartial-terminal Steiner trees

Mathematics Subject Classification ID

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

Related Items (1)

A new approach for the multiobjective minimum spanning tree

Cites Work

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

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