nach oben

Journal of Combinatorial Optimization

Erschienen in:

29.11.2019

Degree bounded bottleneck spanning trees in three dimensions

verfasst von: Patrick J. Andersen, Charl J. Ras

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Nontrivial path covers of graphs: existence, minimization and maximization

Nächster Artikel Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Degree bounded bottleneck spanning trees in three dimensions
verfasst von: Patrick J. Andersen
Charl J. Ras
Publikationsdatum: 29.11.2019
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2020
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00490-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2020

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

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

Price of dependence: stochastic submodular maximization with dependent items

Domination and matching in power and generalized power hypergraphs

A new approximate cluster deletion algorithm for diamond-free graphs

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