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

DOI10.1016/J.JDA.2015.10.003zbMATH Open1343.68317OpenAlexW2194722907MaRDI QIDQ891823FDOQ891823

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

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

zbMATH Keywords

approximation algorithmsSteiner tree problempartial-terminal Steiner trees

Mathematics Subject Classification ID

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

Cites Work

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

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)