Algorithms for Euclidean degree bounded spanning tree problems

DOI10.1142/S0218195919500031MaRDI QIDQ5197492zbMATH OpenOpenAlexFDO

Authors Patrick Andersen, C. J. Ras

Publication date 24 September 2019

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

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

zbMATH Keywords

bottleneck objectivebounded degreecombinatorial optimisationdiscrete geometryheuristic algorithmsminimum spanning trees

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Given a set of points in the Euclidean plane, the Euclidean extit{$delta$-minimum spanning tree} ($delta$-MST) problem is the problem of finding a spanning tree with maximum degree no more than $delta$ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean extit{$delta$-minimum bottleneck spanning tree} ($delta$-MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When $deltaleq4$, these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested.

Recommendations

• Minimum bottleneck spanning trees with degree bounds
• Degree bounded bottleneck spanning trees in three dimensions
• Degree-bounded minimum spanning trees
• Euclidean bottleneck bounded-degree spanning tree ratios
• Euclidean bounded-degree spanning tree ratios

Cites work

• Algorithms for Euclidean degree bounded spanning tree problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An optimal minimum spanning tree algorithm
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approaching 23 for the s-t-path TSP
• Degree-bounded minimum spanning trees
• Euclidean bounded-degree spanning tree ratios
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Improving Christofides' algorithm for the s-t path TSP
• Low-Degree Spanning Trees of Small Weight
• Matroids and the greedy algorithm
• Minimum bottleneck spanning trees with degree bounds
• On the Cube of a Graph
• On the History of the Minimum Spanning Tree Problem
• On the number of leaves of a euclidean minimal spanning tree
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On two geometric problems related to the travelling salesman problem
• The Euclidean degree-4 minimum spanning tree problem is NP-hard
• The Min-Max Spanning Tree Problem and some extensions
• The traveling salesman problem: An overview of exact and approximate algorithms
• Transitions in geometric minimum spanning trees
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(6)

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

This page was built for publication: Algorithms for Euclidean degree bounded spanning tree problems

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