Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts

Authors Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Michiel Smid



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.27.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Jean-Lou De Carufel
Carsten Grimm
Anil Maheshwari
Michiel Smid

Cite AsGet BibTex

Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid. Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SWAT.2016.27

Abstract

We seek to augment a geometric network in the Euclidean plane with shortcuts to minimize its continuous diameter, i.e., the largest network distance between any two points on the augmented network. Unlike in the discrete setting where a shortcut connects two vertices and the diameter is measured between vertices, we take all points along the edges of the network into account when placing a shortcut and when measuring distances in the augmented network. We study this network augmentation problem for paths and cycles. For paths, we determine an optimal shortcut in linear time. For cycles, we show that a single shortcut never decreases the continuous diameter and that two shortcuts always suffice to reduce the continuous diameter. Furthermore, we characterize optimal pairs of shortcuts for convex and non-convex cycles. Finally, we develop a linear time algorithm that produces an optimal pair of shortcuts for convex cycles. Apart from the algorithms, our results extend to rectifiable curves. Our work reveals some of the underlying challenges that must be overcome when addressing the discrete version of this network augmentation problem, where we minimize the discrete diameter of a network with shortcuts that connect only vertices.
Keywords
  • Network Augmentation
  • Shortcuts
  • Diameter
  • Paths
  • Cycles

Metrics

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

References

  1. Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid. Minimizing the continuous diameter when augmenting paths and cycles with shortcuts. This is the full version of this paper., 2015. URL: http://arxiv.org/abs/1512.02257.
  2. 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.
  3. 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. URL: http://dx.doi.org/10.1137/050635675.
  4. 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.
  5. 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.
  6. Ulrike Große, Joachim Gudmundsson, Christian Knauer, Michiel Smid, and Fabian Stehn. Fast algorithms for diameter-optimally augmenting paths. In 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), pages 678-688, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_55.
  7. 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. URL: http://dx.doi.org/10.1016/0167-6377(92)90007-P.
  8. Jun Luo and Christian Wulff-Nilsen. Computing best and worst shortcuts of graphs embedded in metric spaces. In 19th International Symposium on Algorithms and Computation (ISAAC 2008), pages 764-775, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92182-0_67.
  9. 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.
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