LIPIcs.ISAAC.2018.40.pdf
- Filesize: 0.53 MB
- 13 pages
Document
Almost Optimal Algorithms for Diameter-Optimally Augmenting Trees
Author
Davide Bilò 
-
Part of:
Volume:
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-12-06
File
Document Identifiers
Author Details
Cite As Get BibTex
Davide Bilò. Almost Optimal Algorithms for Diameter-Optimally Augmenting Trees. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.40
Abstract
We consider the problem of augmenting an n-vertex tree with one shortcut in order to minimize the diameter of the resulting graph. The tree is embedded in an unknown space and we have access to an oracle that, when queried on a pair of vertices u and v, reports the weight of the shortcut (u,v) in constant time. Previously, the problem was solved in O(n^2 log^3 n) time for general weights [Oh and Ahn, ISAAC 2016], in O(n^2 log n) time for trees embedded in a metric space [Große et al., https://arxiv.org/abs/1607.05547], and in O(n log n) time for paths embedded in a metric space [Wang, WADS 2017]. Furthermore, a (1+epsilon)-approximation algorithm running in O(n+1/epsilon^3) has been designed for paths embedded in R^d, for constant values of d [Große et al., ICALP 2015].
The contribution of this paper is twofold: we address the problem for trees (not only paths) and we also improve upon all known results. More precisely, we design a time-optimal O(n^2) time algorithm for general weights. Moreover, for trees embedded in a metric space, we design (i) an exact O(n log n) time algorithm and (ii) a (1+epsilon)-approximation algorithm that runs in O(n+ epsilon^{-1}log epsilon^{-1}) time.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
- Theory of computation → Approximation algorithms analysis
Keywords
- Graph diameter
- augmentation problem
- trees
- time-efficient algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Noga Alon, András Gyárfás, and Miklós Ruszinkó. Decreasing the diameter of bounded degree graphs. Journal of Graph Theory, 35(3):161-172, 2000. URL: http://dx.doi.org/10.1002/1097-0118(200011)35:3%3C161::AID-JGT1%3E3.0.CO;2-Y.
- Davide Bilò, Luciano Gualà, and Guido Proietti. Improved approximability and non-approximability results for graph diameter decreasing problems. Theor. Comput. Sci., 417:12-22, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2011.05.014.
- Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel H. M. Smid. Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts. In Rasmus Pagh, editor, 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, volume 53 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.27.
- Jean-Lou De Carufel, Carsten Grimm, Stefan Schirra, and Michiel H. M. Smid. Minimizing the Continuous Diameter When Augmenting a Tree with a Shortcut. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, volume 10389 of Lecture Notes in Computer Science, pages 301-312. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62127-2_26.
- Victor Chepoi and Yann Vaxès. Augmenting Trees to Meet Biconnectivity and Diameter Constraints. Algorithmica, 33(2):243-262, 2002. URL: http://dx.doi.org/10.1007/s00453-001-0113-8.
- F. R. K. Chung and M. R. Garey. Diameter bounds for altered graphs. Journal of Graph Theory, 8(4):511-534, 1984. URL: http://dx.doi.org/10.1002/jgt.3190080408.
- Erik D. Demaine and Morteza Zadimoghaddam. Minimizing the Diameter of a Network Using Shortcut Edges. In Haim Kaplan, editor, Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, volume 6139 of Lecture Notes in Computer Science, pages 420-431. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13731-0_39.
- Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, and Luke Mathieson. Augmenting Graphs to Minimize the Diameter. Algorithmica, 72(4):995-1010, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9886-4.
- Yong Gao, Donovan R. Hare, and James Nastos. The parametric complexity of graph diameter augmentation. Discrete Applied Mathematics, 161(10-11):1626-1631, 2013. URL: http://dx.doi.org/10.1016/j.dam.2013.01.016.
- Ulrike Große, Joachim Gudmundsson, Christian Knauer, Michiel H. M. Smid, and Fabian Stehn. Fast Algorithms for Diameter-Optimally Augmenting Paths. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, volume 9134 of Lecture Notes in Computer Science, pages 678-688. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_55.
- Ulrike Große, Joachim Gudmundsson, Christian Knauer, Michiel H. M. Smid, and Fabian Stehn. Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees. CoRR, abs/1607.05547, 2016. URL: http://arxiv.org/abs/1607.05547.
- John Hershberger. Finding the Upper Envelope of n Line Segments in it O(n log n) Time. Inf. Process. Lett., 33(4):169-174, 1989. URL: http://dx.doi.org/10.1016/0020-0190(89)90136-1.
- Toshimasa Ishii. Augmenting Outerplanar Graphs to Meet Diameter Requirements. Journal of Graph Theory, 74(4):392-416, 2013. URL: http://dx.doi.org/10.1002/jgt.21719.
-
Chung-Lun Li, S.Thomas McCormick, and David Simchi-Levi. On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum diameter edge addition problems. Operations Research Letters, 11(5):303-308, 1992.
- Nimrod Megiddo. Applying Parallel Computation Algorithms in the Design of Serial Algorithms. J. ACM, 30(4):852-865, 1983. URL: http://dx.doi.org/10.1145/2157.322410.
- Eunjin Oh and Hee-Kap Ahn. A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree. In Seok-Hee Hong, editor, 27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia, volume 64 of LIPIcs, pages 59:1-59:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.59.
- Anneke A. Schoone, Hans L. Bodlaender, and Jan van Leeuwen. Diameter increase caused by edge deletion. Journal of Graph Theory, 11(3):409-427, 1987. URL: http://dx.doi.org/10.1002/jgt.3190110315.
- Haitao Wang. An Improved Algorithm for Diameter-Optimally Augmenting Paths in a Metric Space. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, volume 10389 of Lecture Notes in Computer Science, pages 545-556. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62127-2_46.