Top

Journal of Combinatorial Optimization

Published in:

29-11-2019

Degree bounded bottleneck spanning trees in three dimensions

Authors: Patrick J. Andersen, Charl J. Ras

Published in: Journal of Combinatorial Optimization | Issue 2/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Nontrivial path covers of graphs: existence, minimization and maximization

next article Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Agarwal PK, Edelsbrunner H, Schwarzkopf O, Welzl E (1991) Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput Geom 6(3):407–422MathSciNetMATHCrossRef

Akyildiz IF, Pompili D, Melodia T (2005) Underwater acoustic sensor networks: research challenges. Ad Hoc Netw 3(3):257–279CrossRef

Andersen PJ, Ras CJ (2016) Minimum bottleneck spanning trees with degree bounds. Networks 68(4):302–314MathSciNetMATHCrossRef

Andersen PJ, Ras CJ (2019) Algorithms for Euclidean degree bounded spanning tree problems. Int J Comput Geom Appl 29(02):121–160MathSciNetMATHCrossRef

Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 45(5):753–782MathSciNetMATHCrossRef

Berman O, Einav D, Handler G (1990) The constrained bottleneck problem in networks. Oper Res 38(1):178–181MathSciNetMATHCrossRef

Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. Math Proc Camb Philos Soc 55(4):299–327MathSciNetMATHCrossRef

Brazil M, Ras CJ, Thomas DA (2012) The bottleneck 2-connected \(k\)-Steiner network problem for \(k \ge 2\). Discrete Appl Math 160(7–8):1028–1038MathSciNetMATHCrossRef

Camerini PM (1978) The min-max spanning tree problem and some extensions. Inf Process Lett 7(1):10–14MathSciNetMATHCrossRef

Chan TM (2004) Euclidean bounded-degree spanning tree ratios. Discrete Comput Geom 32(2):177–194MathSciNetMATHCrossRef

Cieslik D (1991) The 1-Steiner-minimal-tree problem in Minkowski-spaces. Optimization 22(2):291–296MathSciNetMATHCrossRef

Deo N, Micikevicius P (1999) A heuristic for a leaf constrained minimum spanning tree problem. Congr Numer 141:61–272MathSciNetMATH

Fampa M, Anstreicher KM (2008) An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space. Discrete Optim 5(2):530–540MathSciNetMATHCrossRef

Francke A, Hoffmann M (2009) The Euclidean degree-4 minimum spanning tree problem is NP-hard. In: Proceedings of the twenty-fifth annual symposium on computational geometry, ACM, pp 179–188

Garey MR, Johnson DS (1979) Computers and Intractability: a guide to the theory of NP-completeness. Freeman W.H., New YorkMATH

Graham RL, Hell P (1985) On the history of the minimum spanning tree problem. Ann Hist Comput 7(1):43–57MathSciNetMATHCrossRef

Khuller S, Raghavachari B, Young N (1996) Low-degree spanning trees of small weight. SIAM J Comput 25(2):355–368MathSciNetMATHCrossRef

Könemann J, Ravi R (2002) A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. SIAM J Comput 31(6):1783–1793MathSciNetMATHCrossRef

Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7(1):48–50MathSciNetMATHCrossRef

Larman DG, Zong C (1999) On the kissing numbers of some special convex bodies. Discrete Comput Geom 21(2):233–242MathSciNetMATHCrossRef

Martin H, Swanepoel KJ (2006) Low-degree minimal spanning trees in normed spaces. Appl Math Lett 19(2):122–125MathSciNetMATHCrossRef

Monma C, Suri S (1992) Transitions in geometric minimum spanning trees. Discrete Comput Geom 8(3):265–293MathSciNetMATHCrossRef

Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237–244MATHCrossRef

Papadimitriou CH, Vazirani UV (1984) On two geometric problems related to the travelling salesman problem. J Algorithms 5(2):231–246MathSciNetMATHCrossRef

Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36(6):1389–1401CrossRef

Punnen AP, Nair KPK (1996) An improved algorithm for the constrained bottleneck spanning tree problem. INFORMS J Comput 8(1):41–44MATHCrossRef

Ravi R, Goemans MX (1996) The constrained minimum spanning tree problem. In: Scandinavian Workshop on Algorithm Theory, Springer, pp 66–75

Robins G, Salowe JS (1995) Low-degree minimum spanning trees. Discrete Comput Geom 14(2):151–165MathSciNetMATHCrossRef

Sarrafzadeh M, Wong CK (1992) Bottleneck Steiner trees in the plane. IEEE Trans Comput 3:370–374MathSciNetMATHCrossRef

Smith WD (1992) How to find Steiner minimal trees in Euclidean \(d\)-space. Algorithmica 7(1–6):137–177MathSciNetMATHCrossRef

Talata I (1999) The translative kissing number of tetrahedra is 18. Discrete Comput Geom 22(2):231–248MathSciNetMATHCrossRef

Tassiulas L (1997) Worst case length of nearest neighbor tours for the Euclidean traveling salesman problem. SIAM J Discrete Math 10(2):171–179MathSciNetMATHCrossRef

Thomas DA, Wen JF (2014) Euclidean Steiner trees optimal with respect to swapping 4-point subtrees. Optim Lett 8(4):1337–1359MathSciNetMATHCrossRef

Toth LF (1975) On Hadwiger numbers and Newton numbers of a convex body. Studia Sci Math Hungar 10:111–115MathSciNetMATH

Vaidya PM (1988) Minimum spanning trees in \(k\)-dimensional space. SIAM J Comput 17(3):572–582MathSciNetMATHCrossRef

Wu BY, Chao KM (2004) Spanning trees and optimization problems. Chapman and Hall, New YorkMATHCrossRef

Yao ACC (1982) On constructing minimum spanning trees in \(k\)-dimensional spaces and related problems. SIAM J Comput 11(4):721–736MathSciNetMATHCrossRef

Title: Degree bounded bottleneck spanning trees in three dimensions
Authors: Patrick J. Andersen
Charl J. Ras
Publication date: 29-11-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00490-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2020

The average covering tree value for directed graph games

A patient flow scheduling problem in ophthalmology clinic solved by the hybrid EDA–VNS algorithm

Domination and matching in power and generalized power hypergraphs

Local search strikes again: PTAS for variants of geometric covering and packing

Equitable partition of graphs into induced linear forests

A new upper bound on the work function algorithm for the k-server problem

Premium Partner