Item Details

On the Maximum Degree of Minimum Spanning Trees

Robins, Gabriel; Salowe, Jeffrey
Format
Report
Author
Robins, Gabriel
Salowe, Jeffrey
Abstract
Motivated by practical VLSI applications, we study the maximum vertex degree in a minimum spanning tree (MST) under arbitrary LP metrics. We show that the maximum vertex degree in a maximum - degree LP MST equals the Hadwiger number of the corresponding unit ball. We then determine the maximum vertex degree in a minimum-degree LP MST; towards this end, we define the MST number, which is closely related to the Hadwiger number. We bound Hadwiger and MST numbers for arbitrary LP metrics, and focus on the L1 metric, where little was known. We show that the MST number of a diamond is 4, and that for the octahedron the Hadwiger number is 18 and the MST number is either 13 or 14. We also give an exponential lower bound on the MST number for an LP unit ball. Implications to LP minimum spanning trees and related problems are explored. Note: Abstract extracted from PDF file via OCR
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1993
Published Date
1993
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online