On the clustered Steiner tree problem

DOI10.1007/978-3-319-03780-6_6MaRDI QIDQ2867108zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmgraph algorithmNP-hardnessSteiner tree

Mathematics Subject Classification ID

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

Recommendations

• On the clustered Steiner tree problem
• The Clustered Selected-Internal Steiner Tree Problem
• On the minimum routing cost clustered tree problem
• Improved Approximations for the Steiner Tree Problem
• On the terminal Steiner tree problem.

Cites work

• A better constant-factor approximation for selected-internal Steiner minimum tree
• A note on the terminal Steiner tree problem
• Algorithms for terminal Steiner trees
• An 11/6-approximation algorithm for the network Steiner problem
• An improved approximation algorithm for the clustered traveling salesman problem
• An improved LP-based approximation for Steiner tree
• Approximating the selected-internal Steiner tree
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Eight-fifth approximation for the path TSP
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303564 (Why is no real title available?)
• Introduction to algorithms
• On approximation algorithms for the terminal Steiner tree problem
• On the full and bottleneck full Steiner tree problems
• On the terminal Steiner tree problem.
• Spanning Trees and Optimization Problems
• The Complexity of Computing Steiner Minimal Trees
• The full Steiner tree problem
• The internal Steiner tree problem: Hardness and approximations
• The Rectilinear Steiner Tree Problem is NP-Complete
• Tighter Bounds for Graph Steiner Tree Approximation
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(7)

• On the clustered Steiner tree problem
• On the minimum routing cost clustered tree problem
• Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
• Vertices removal for feasibility of clustered spanning trees
• On the Optimal Stars Clustering Tree Problem
• Clustered spanning tree -- conditions for feasibility
• The Clustered Selected-Internal Steiner Tree Problem

This page was built for publication: On the clustered Steiner tree problem

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