The Euclidean degree-4 minimum spanning tree problem is NP-hard

DOI10.1145/1542362.1542399MaRDI QIDQ5370716zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 20 October 2017

Published in Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1542362.1542399

zbMATH Keywords

bounded-degree graphsdegree-constricted graphsdegree-restricted graphsgeometric graphsgeometric optimizationNP-completereductionspanning trees

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The realization problem for Euclidean minimum spanning trees is NP-hard
• Degree-bounded minimum spanning trees
• Low-Degree Spanning Trees of Small Weight
• The vertex degrees of minimum spanning trees
• md-MST is NP-hard for \(d\geq 3\)

Cited in

(7)

• The realization problem for Euclidean minimum spanning trees is NP-hard
• Euclidean bottleneck bounded-degree spanning tree ratios
• Degree bounded bottleneck spanning trees in three dimensions
• On the area requirements of Euclidean minimum spanning trees
• Low-Degree Spanning Trees of Small Weight
• Algorithms for Euclidean degree bounded spanning tree problems
• Polynomial area bounds for MST embeddings of trees

This page was built for publication: The Euclidean degree-4 minimum spanning tree problem is NP-hard

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