On the Clustered Steiner Tree Problem

DOI10.1007/978-3-319-03780-6_6zbMath1406.68093OpenAlexW2402805681MaRDI QIDQ2867108

Bang Ye Wu

Publication date: 10 December 2013

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03780-6_6

zbMATH Keywords

graph algorithmapproximation algorithmNP-hardnessSteiner tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved approximation algorithm for the clustered 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
• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• On the terminal Steiner tree problem.
• The internal Steiner tree problem: Hardness and approximations
• An 11/6-approximation algorithm for the network Steiner problem
• Algorithms for terminal Steiner trees
• An improved LP-based approximation for steiner tree
• On the Full and Bottleneck Full Steiner Tree Problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Spanning Trees and Optimization Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Eight-Fifth Approximation for the Path TSP
• Tighter Bounds for Graph Steiner Tree Approximation

This page was built for publication: On the Clustered Steiner Tree Problem