On the clustered Steiner tree problem

DOI10.1007/S10878-014-9772-7MaRDI QIDQ2355992zbMATH OpenOpenAlexFDO

Authors Bang Ye Wu, Chen-Wan Lin

Publication date 28 July 2015

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-014-9772-7

zbMATH Keywords

graph theoryapproximation algorithmNP-hardSteiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• On the clustered Steiner tree problem
• The Clustered Selected-Internal Steiner Tree Problem
• scientific article; zbMATH DE number 1834686
• scientific article; zbMATH DE number 1182759
• Steiner tree problems
• Steiner tree problems
• On the restricted \(k\)-Steiner tree problem
• On the minimum routing cost clustered tree problem
• The Steiner tree problem
• On the approximability of the Steiner tree problem.

Cites work

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

Cited in

(9)

• The General Steiner Tree-Star problem.
• Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem
• On the minimum routing cost clustered tree problem
• On the clustered Steiner tree problem
• The Clustered Selected-Internal Steiner Tree Problem
• Two-level rectilinear Steiner trees
• On the Optimal Stars Clustering Tree Problem
• Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
• The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm

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 Q2355992)