Algorithms for Euclidean Degree Bounded Spanning Tree Problems

DOI10.1142/S0218195919500031zbMath1430.68353arXiv1809.09348OpenAlexW2973878682MaRDI QIDQ5197492

Patrick J. Andersen, Charl 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

discrete geometryheuristic algorithmsminimum spanning treescombinatorial optimisationbounded degreebottleneck objective

Mathematics Subject Classification ID

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

Related Items (4)

Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ DEGREE BOUNDED GEOMETRIC SPANNING TREES WITH A BOTTLENECK OBJECTIVE FUNCTION ⋮ Euclidean bottleneck bounded-degree spanning tree ratios

Cites Work

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

This page was built for publication: Algorithms for Euclidean Degree Bounded Spanning Tree Problems