On the clustered Steiner tree problem

DOI10.1007/S10878-014-9772-7zbMATH Open1327.90271OpenAlexW1986593951MaRDI QIDQ2355992FDOQ2355992

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

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.

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)

Cites Work

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

Cited In (8)

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