Degree bounded bottleneck spanning trees in three dimensions

Patrick J. Andersen () and Charl J. Ras
Additional contact information
Patrick J. Andersen: The University of Melbourne
Charl J. Ras: The University of Melbourne

Journal of Combinatorial Optimization, 2020, vol. 39, issue 2, No 10, 457-491

Abstract: Abstract The geometric $$\delta $$δ-minimum spanning tree problem ($$\delta $$δ-MST) is the problem of finding a minimum spanning tree for a set of points in a normed vector space, such that no vertex in the tree has a degree which exceeds $$\delta $$δ, and the sum of the lengths of the edges in the tree is minimum. The similarly defined geometric $$\delta $$δ-minimum bottleneck spanning tree problem ($$\delta $$δ-MBST), is the problem of finding a degree bounded spanning tree such that the length of the longest edge is minimum. For point sets that lie in the Euclidean plane, both of these problems have been shown to be NP-hard for certain specific values of $$\delta $$δ. In this paper, we investigate the $$\delta $$δ-MBST problem in 3-dimensional Euclidean space and 3-dimensional rectilinear space. We show that the problems are NP-hard for certain values of $$\delta $$δ, and we provide inapproximability results for these cases. We also describe new approximation algorithms for solving these 3-dimensional variants, and then analyse their worst-case performance.

Keywords: Minimum spanning trees; Bottleneck objective; Approximation algorithms; Discrete geometry; Bounded degree; Combinatorial optimisation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00490-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:2:d:10.1007_s10878-019-00490-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00490-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().