On the minimum routing cost clustered tree problem

DOI10.1007/S10878-016-0026-8MaRDI QIDQ2359809zbMATH OpenOpenAlexFDO

Authors Chen-Wan Lin, Bang Ye Wu

Publication date 22 June 2017

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

Full work available at URL https://doi.org/10.1007/s10878-016-0026-8

zbMATH Keywords

approximation algorithmgraph algorithmNP-hardspanning tree

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Exact algorithms for minimum routing cost trees
• On the clustered Steiner tree problem
• On the clustered Steiner tree problem
• On the complexity of an optimal routing tree problem
• The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
• scientific article; zbMATH DE number 1303537
• Minimum weight clustered dominating tree problem
• The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A linear-time algorithm to compute a MAD tree of an interval graph
• A note on two problems in connexion with graphs
• A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
• A two-patch model for the optimal management of a fishing resource considering a marine protected area
• An improved approximation algorithm for the clustered traveling salesman problem
• Approximation algorithms for somek-source shortest paths spanning tree problems
• Approximation algorithms for the shortest total path length spanning tree problem
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Distributed approximation of minimum routing cost trees
• Exact algorithms for minimum routing cost trees
• Finding best swap edges minimizing the routing cost of a spanning tree
• Generalized network design problems.
• Introduction to algorithms
• Light graphs with small routing cost
• On the clustered Steiner tree problem
• On the intercluster distance of a tree metric
• PTAS's for some metric \(p\)-source communication spanning tree problems
• Spanning Trees and Optimization Problems
• The checkpoint problem
• The swap edges of a multiple-sources routing tree
• Worst-Case Analysis of Network Design Problem Heuristics

Cited in

(13)

• Decomposing the feasibility of clustered spanning tree by paths
• Minimum weight clustered dominating tree problem
• Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem
• On the clustered Steiner tree problem
• On the clustered Steiner tree problem
• Clustered spanning tree -- conditions for feasibility
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Vertices removal for feasibility of clustered spanning trees
• Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
• 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
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
• The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm

This page was built for publication: On the minimum routing cost clustered tree problem

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