The minimum spanning tree problem with non-terminal set

DOI10.1016/J.IPL.2012.06.012MaRDI QIDQ456089zbMATH OpenOpenAlexFDO

Authors Tongquan Zhang, Ying Yin

Publication date 23 October 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.06.012

zbMATH Keywords

approximation algorithmsminimum spanning tree problemnon-terminal setNP-completeness

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Minimum Spanning Tree with Neighborhoods
• On the generalized minimum spanning tree problem
• scientific article; zbMATH DE number 1003287
• The Minimum Spanning Tree Problem with Time Window Constraints

Cites work

• A note on the terminal Steiner tree problem
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Algorithms for terminal Steiner trees
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On approximation algorithms for the terminal Steiner tree problem

Cited in

(3)

• On the statistical evaluation of algorithmic's computational experimentation with infeasible solutions
• scientific article; zbMATH DE number 910870 (Why is no real title available?)
• Finding a minimum spanning tree with a small non-terminal set

This page was built for publication: The minimum spanning tree problem with non-terminal set

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