On the clustered Steiner tree problem

DOI10.1007/s10878-014-9772-7zbMath1327.90271OpenAlexW1986593951MaRDI QIDQ2355992

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

approximation algorithmgraph theoryNP-hardSteiner tree

Mathematics Subject Classification ID

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

Related Items (6)

On the minimum routing cost clustered tree problem ⋮ Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem ⋮ Two-level rectilinear Steiner trees ⋮ The Clustered Selected-Internal Steiner 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

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
• Node-weighted Steiner tree approximation in unit disk graphs
• Approximating the selected-internal Steiner tree
• On approximation algorithms for the terminal Steiner tree problem
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Two variations of the minimum Steiner 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
• Minimum diameter cost-constrained Steiner trees
• 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
• Reducibility among Combinatorial Problems
• Tighter Bounds for Graph Steiner Tree Approximation

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