No Access

Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees

Ulrike Große

Institut für Angewandte Informatik, Universität Bayreuth, Universitätsstrasse 30, 95447 Bayreuth, Germany

E-mail Address: ulrike.grosse@uni-bayreuth.de

Search for more papers by this author

Christian Knauer

Institut für Angewandte Informatik, Universität Bayreuth, Universitätsstrasse 30, 95447 Bayreuth, Germany

E-mail Address: christian.knauer@uni-bayreuth.de

Search for more papers by this author

Fabian Stehn

Institut für Angewandte Informatik, Universität Bayreuth, Universitätsstrasse 30, 95447 Bayreuth, Germany

E-mail Address: fabian.stehn@uni-bayreuth.de

Search for more papers by this author

Joachim Gudmundsson

School of Information Technologies, J12, The University of Sydney, NSW 2006, Sydney, Australia

E-mail Address: joachim.gudmundsson@sydney.edu.au

Search for more papers by this author

, and

Michiel Smid

School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Canada K1S 5B6, Canada

E-mail Address: michiel@scs.carleton.ca

Search for more papers by this author

https://doi.org/10.1142/S0129054119500060Cited by:2 (Source: Crossref)

Abstract

We consider the problem of augmenting an $n$ -vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in $O (n {log}^{3} n)$ time, and (ii) the input graph is a tree, running in $O (n^{2} log n)$ time. We also present an algorithm for paths that computes a $(1 + 𝜀)$ -approximation in $O (n + 1 / 𝜀^{3})$ time.

Communicated by Marek Chrobak

Keywords:

References

1. N. Alon, A. Gyárfás and M. Ruszinkó, Decreasing the diameter of bounded degree graphs, Journal of Graph Theory 35 (1999) 161–172. Crossref, Web of Science, Google Scholar
2. M. D. Berg, O. Cheong, M. V. Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications (Springer-Verlag TELOS, Santa Clara, CA, USA, 2008). Crossref, Google Scholar
3. D. Bilò, L. Gualà and G. Proietti, Improved approximability and non-approximability results for graph diameter decreasing problems, Theoretical Computer Science 417 (2012) 12–22. Crossref, Web of Science, Google Scholar
4. J.-L. D. Carufel, C. Grimm, A. Maheshwari and M. Smid, Minimizing the continuous diameter when augmenting paths and cycles with shortcuts, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) 53 (2016), pp. 27:1–27:14. Google Scholar
5. V. Chepoi and Y. Vaxès, Augmenting trees to meet biconnectivity and diameter constraints, Algorithmica 33(2) (2002) 243–262. Crossref, Web of Science, Google Scholar
6. F. R. K. Chung and M. R. Garey, Diameter bounds for altered graphs, Journal of Graph Theory 8(4) (1984) 511–534. Crossref, Web of Science, Google Scholar
7. T. H. Cormen, C. Stein, R. L. Rivest and C. E. Leiserson, Introduction to Algorithms, 1st edn. (MIT Press and McGraw-Hill, 1990). Google Scholar
8. J.-L. De Carufel, C. Grimm, S. Schirra and M. Smid, Minimizing the continuous diameter when augmenting a tree with a shortcut, Algorithms and Data Structures, eds. F. Ellen, A. Kolokolova and J.-R. Sack (Springer International Publishing, Cham, 2017), pp. 301–312. Crossref, Google Scholar
9. Y. Dodis and S. Khanna, Designing networks with bounded pairwise distance, Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), (1999), pp. 750–759. Google Scholar
10. P. Erdős, A. Gyárfás and M. Ruszinkó, How to decrease the diameter of triangle-free graphs, Combinatorica 18(4) (1998) 493–501. Crossref, Web of Science, Google Scholar
11. M. Farshi, P. Giannopoulos and J. Gudmundsson, Improving the stretch factor of a geometric network by edge augmentation, SIAM Journal on Computing 38(1) (2005) 226–240. Crossref, Web of Science, Google Scholar
12. F. Frati, S. Gaspers, J. Gudmundsson and L. Mathieson, Augmenting graphs to minimize the diameter, Algorithmica (2014) 1–16. Web of Science, Google Scholar
13. Y. Gao, D. R. Hare and J. Nastos, The parametric complexity of graph diameter augmentation, Discrete Applied Mathematics 161(10–11) (2013) 1626–1631. Crossref, Web of Science, Google Scholar
14. U. Große, J. Gudmundsson, C. Knauer, M. Smid and F. Stehn, Fast algorithms for diameter-optimally augmenting paths, Automata, Languages, and Programming, eds. M. M. Halldórsson, K. Iwama, N. Kobayashi and B. Speckmann (Springer, Berlin, Heidelberg, 2015), pp. 678–688. Crossref, Google Scholar
15. T. Ishii, Augmenting outerplanar graphs to meet diameter requirements, Journal of Graph Theory 74 (2013) 392–416. Crossref, Web of Science, Google Scholar
16. S. Kapoor and M. Sarwat, Bounded-diameter minimum-cost graph problems, Theory of Computing Systems 41(4) (2007) 779–794. Crossref, Web of Science, Google Scholar
17. C.-L. Li, S. T. McCormick and D. Simchi-Levi, On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems, Operations Research Letters 11(5) (1992) 303–308. Crossref, Web of Science, Google Scholar
18. J. Luo and C. Wulff-Nilsen, Computing best and worst shortcuts of graphs embedded in metric spaces, 19th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, (Springer, 2008). Google Scholar
19. N. Megiddo, Combinatorial optimization with rational objective functions, Math. Oper. Res. 4 (1979) 414–424. Crossref, Google Scholar
20. N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, Journal of the ACM 30(4) (1983) 852–865. Crossref, Web of Science, Google Scholar
21. E. Oh and H.-K. Ahn, A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree, 27th International Symposium on Algorithms and Computation (ISAAC 2016), ed. S.-H. Hong, Leibniz International Proceedings in Informatics (LIPIcs) 64, (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016), pp. 59:1–59:12. Google Scholar
22. I. Rutter and A. Wolff, Augmenting the connectivity of planar and geometric graphs, Journal of Graph Algorithms and Applications 16(2) (2012) 599–628. Crossref, Google Scholar
23. A. A. Schoone, H. L. Bodlaender and J. van Leeuwen, Diameter increase caused by edge deletion, Journal of Graph Theory 11 (1997) 409–427. Crossref, Web of Science, Google Scholar
24. R. van Oostrum and R. C. Veltkamp, Parametric search made practical, Computational Geometry 28(2) (2004) 75–88. Crossref, Web of Science, Google Scholar
25. H. Wang, An improved algorithm for diameter-optimally augmenting paths in a metric space, Algorithms and Data Structures, eds. F. Ellen, A. Kolokolova and J.-R. Sack (Springer International Publishing, Cham, 2017), pp. 545–556. Crossref, Google Scholar
26. C. Wulff-Nilsen, Computing the dilation of edge-augmented graphs in metric spaces, Computational Geometry — Theory and Applications 43(2) (2010) 68–72. Crossref, Web of Science, Google Scholar
27. B. Yang, Euclidean chains and their shortcuts, Theoretical Computer Science 497 (2013) 55–67. Crossref, Web of Science, Google Scholar