Degree bounded bottleneck spanning trees in three dimensions

DOI10.1007/S10878-019-00490-2zbMATH Open1439.90058arXiv1812.11177OpenAlexW2990929878WikidataQ126641714 ScholiaQ126641714MaRDI QIDQ2292155FDOQ2292155

Patrick Andersen, C. J. Ras

Publication date: 3 February 2020

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

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)