On the Clustered Steiner Tree Problem

DOI10.1007/978-3-319-03780-6_6zbMath1406.68093MaRDI 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 algorithm; approximation algorithm; NP-hardness; Steiner tree

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

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