The Euclidean degree-4 minimum spanning tree problem is NP-hard
From MaRDI portal
Publication:5370716
DOI10.1145/1542362.1542399zbMath1380.68197OpenAlexW1977267311MaRDI QIDQ5370716
No author found.
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
reductiongeometric graphsNP-completegeometric optimizationspanning treesbounded-degree graphsdegree-constricted graphsdegree-restricted graphs
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On the area requirements of Euclidean minimum spanning trees, Polynomial area bounds for MST embeddings of trees, Algorithms for Euclidean Degree Bounded Spanning Tree Problems, Degree bounded bottleneck spanning trees in three dimensions, Euclidean bottleneck bounded-degree spanning tree ratios