Low-degree minimum spanning trees

DOI10.1007/BF02570700zbMath0827.05020MaRDI QIDQ1895968

Yanyan Li

Publication date: 27 November 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131396

zbMATH Keywords

minimum spanning treemaximum vertex degreeHadwiger number

Mathematics Subject Classification ID

Trees (05C05) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Related Items

Improved approximation algorithms for single-tiered relay placement ⋮ Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ Small degree out‐branchings ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees ⋮ Kissing numbers and the centered maximal operator ⋮ Low-degree minimal spanning trees in normed spaces ⋮ Wireless network design via 3-decompositions ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Antipodal Hadwiger numbers of finite-dimensional Banach spaces ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points ⋮ A unifying model for locally constrained spanning tree problems ⋮ New lower bounds for the Hadwiger numbers of \(\ell_p\) balls for \(p<2\) ⋮ Degree-bounded minimum spanning trees ⋮ The vertex degrees of minimum spanning trees ⋮ Efficient minimum spanning tree construction with Delaynay triangulation ⋮ Relay placement for two-connectivity ⋮ A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On computing all north-east nearest neighbors in the \(L_ 1\) metric
• Efficient algorithms for agglomerative hierarchical clustering methods
• Unsolved problems in geometry
• Transitions in geometric minimum spanning trees
• On two geometric problems related to the travelling salesman problem
• The 1-steiner tree problem
• Three-Dimensional Integrated Circuit Layout
• On the History of the Minimum Spanning Tree Problem