Degree bounded bottleneck spanning trees in three dimensions

DOI10.1007/S10878-019-00490-2MaRDI QIDQ2292155zbMATH OpenOpenAlexWikidataFDO

Authors Patrick Andersen, C. J. Ras

Publication date 3 February 2020

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.11177

zbMATH Keywords

discrete geometryapproximation algorithmscombinatorial optimisationminimum spanning treesbounded degreebottleneck objective

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

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.

Recommendations

• Minimum bottleneck spanning trees with degree bounds
• Algorithms for Euclidean degree bounded spanning tree problems
• Degree-bounded minimum spanning trees
• Low-Degree Spanning Trees of Small Weight
• The vertex degrees of minimum spanning trees

Cites work

• scientific article; zbMATH DE number 3551504 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1439455 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• Algorithms for Euclidean degree bounded spanning tree problems
• An Improved Algorithm for the Constrained Bottleneck Spanning Tree Problem
• An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space
• Bottleneck Steiner trees in the plane
• Euclidean Steiner trees optimal with respect to swapping 4-point subtrees
• Euclidean bounded-degree spanning tree ratios
• Euclidean minimum spanning trees and bichromatic closest pairs
• How to find Steiner minimal trees in Euclidean \(d\)-space
• Low-Degree Spanning Trees of Small Weight
• Low-degree minimal spanning trees in normed spaces
• Low-degree minimum spanning trees
• Minimum Spanning Trees in k-Dimensional Space
• Minimum bottleneck spanning trees with degree bounds
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On the History of the Minimum Spanning Tree Problem
• On the kissing numbers of some special convex bodies
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On two geometric problems related to the travelling salesman problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Spanning Trees and Optimization Problems
• The 1-Steiner-Minimal-Tree problem in Minkowski-spaces
• The Constrained Bottleneck Problem in Networks
• The Euclidean degree-4 minimum spanning tree problem is NP-hard
• The Euclidean traveling salesman problem is NP-complete
• The Min-Max Spanning Tree Problem and some extensions
• The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\)
• The constrained minimum spanning tree problem
• The translative kissing number of tetrahedra is 18
• Transitions in geometric minimum spanning trees
• Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem

Cited in

(6)

• Minimum bottleneck spanning trees with degree bounds
• DEGREE BOUNDED GEOMETRIC SPANNING TREES WITH A BOTTLENECK OBJECTIVE FUNCTION
• Algorithms for Euclidean degree bounded spanning tree problems
• Euclidean bottleneck bounded-degree spanning tree ratios
• Three-Dimensional Drawings of Bounded Degree Trees
• Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios

This page was built for publication: Degree bounded bottleneck spanning trees in three dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292155)