The minimum spanning tree problem with non-terminal set

DOI10.1016/j.ipl.2012.06.012zbMath1248.68226OpenAlexW2090857456MaRDI QIDQ456089

Ying Yin, Tongquan Zhang

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

NP-completenessminimum spanning tree problemapproximation algorithmsnon-terminal set

Mathematics Subject Classification ID

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

Related Items (1)

On the statistical evaluation of algorithmic's computational experimentation with infeasible solutions

Cites Work

• Unnamed Item
• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• Algorithms for terminal Steiner trees
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• A Randomized Rounding Approach to the Traveling Salesman Problem

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