Low-degree minimum spanning trees
| Autor: | Gabriel Robins, Jeffrey S. Salowe |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
Unit sphere
Spanning tree Degree (graph theory) Hadwiger number Computer Science::Computational Geometry Minimum spanning tree Theoretical Computer Science Combinatorics Computational Theory and Mathematics Norm (mathematics) Discrete Mathematics and Combinatorics Geometry and Topology Finite set Minimum degree spanning tree Mathematics |
| Zdroj: | Discrete & Computational Geometry. 14:151-165 |
| ISSN: | 1432-0444 0179-5376 |
| DOI: | 10.1007/bf02570700 |
| Popis: | Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that, under theLp norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an even tighter bound for MSTs where the maximum degree is minimized. We give the best-known bounds for the maximum MST degree for arbitraryLp metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite set of points in the rectilinear plane an MST exists with maximum degree of at most 4, and for three-dimensional rectilinear space the maximum possible degree of a minimum-degree MST is either 13 or 14. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink