Document Open Access Logo

A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree

Authors Eunjin Oh, Hee-Kap Ahn

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.59.pdf
  • Filesize: 0.56 MB
  • 12 pages

Document Identifiers

Author Details

Eunjin Oh
Hee-Kap Ahn

Cite AsGet BibTex

Eunjin Oh and Hee-Kap Ahn. A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.59

Abstract

We consider the problem of finding a shortcut connecting two vertices of a graph that minimizes the diameter of the resulting graph. We present an O(n^2 log^3 n)-time algorithm using linear space for the case that the input graph is a tree consisting of n vertices. Additionally, we present an O(n^2 log^3 n)-time algorithm using linear space for a continuous version of this problem.
Keywords
  • Network Augmentation
  • Shortcuts
  • Diameter
  • Trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hee-Kap Ahn, Mohammad Farshi, Christian Knauser, Michiel Smid, and Yajun Wang. Dilation-optimal edge deletion in polygonal cycles. International Journal of Computational Geometry & Applications, 20(1):69-87, 2010. Google Scholar
  2. Noga Alon, Andras Gyarfas, and Miklos Ruszinko. Decreasing the diameter of bounded degree graphs. Journal of Graph Theory, 35(3):161-172, 2000. Google Scholar
  3. F. R. K. Chung and M. R. Garey. Diameter bounds for altered graphs. Journal of Graph Theory, 8(4):511-534, 1984. Google Scholar
  4. Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid. Minimizing the continuous diameter when augmenting paths and cycles with shortcuts. In Proceedings of 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), pages 27:1-27:14, 2016. Google Scholar
  5. Mohammad Farshi, Panos Giannopoulos, and Joachim Gudmundsson. Improving the stretch factor of a geometric network by edge augmentation. SIAM Journal on Computing, 38(1):226-240, 2008. Google Scholar
  6. Ulrike Große, Joachim Gudmundsson, Christian Knauer, Michiel Smid, and Fabian Stehn. Fast algorithms for diameter-optimally augmenting paths. In Proceedings of Automata, Languages, and Programming: 42nd International Colloquium (ICALP 2015), pages 678-688, 2015. Google Scholar
  7. Toshimasa Ishii. Diameter bounds for altered graphs. Journal of Graph Theory, 74(4):392-416, 2013. Google Scholar
  8. Rolf Klein, Christian Knauer, Giri Narasimhan, and Michiel Smid. Exact and approximation algorithms for computing the dilation spectrum of paths, trees, and cycles. In Proceedings of the 16th International Symposium on Algorithms and Computatiom, (ISAAC 2005), pages 849-858, 2005. Google Scholar
  9. Jun Luo and Christian Wulff-Nilsen. Computing best and worst shortcuts of graphs embedded in metric spaces. In Proceedings of the 19th International Symposium on Algorithms and Computatiom, (ISAAC 2008), pages 764-775, 2008. Google Scholar
  10. Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, 1983. Google Scholar
  11. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact