Degree bounded bottleneck spanning trees in three dimensions
| Autor: | Patrick J. Andersen, Charl J. Ras |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences 90C27 Vertex (graph theory) Control and Optimization 0211 other engineering and technologies Discrete geometry 0102 computer and information sciences 02 engineering and technology Minimum spanning tree 01 natural sciences Combinatorics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Mathematics Normed vector space 021103 operations research Spanning tree Euclidean space Applied Mathematics Approximation algorithm Computer Science Applications Computational Theory and Mathematics 010201 computation theory & mathematics Bounded function Computer Science - Computational Geometry Combinatorics (math.CO) MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Combinatorial Optimization. 39:457-491 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-019-00490-2 |
| Popis: | 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. Comment: 35 pages, 22 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink