Document Open Access Logo

Computing Optimal Shortcuts for Networks

Authors Delia Garijo, Alberto Márquez, Natalia Rodríguez, Rodrigo I. Silveira

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.15.pdf
  • Filesize: 0.72 MB
  • 12 pages

Document Identifiers

Author Details

Delia Garijo
  • Departamento de Matemática Aplicada I, Universidad de Sevilla, Spain
Alberto Márquez
  • Departamento de Matemática Aplicada I, Universidad de Sevilla, Spain
Natalia Rodríguez
  • Departamento de Computación, Universidad de Buenos Aires, Argentina
Rodrigo I. Silveira
  • Departament de Matemàtiques, Universitat Politècnica de Catalunya, Spain

Funding

D. G. and R. S. were supported by project MTM2015-63791-R. R. S. was also supported by Gen. Cat. 2017SGR1640 and MINECO through the Ramón y Cajal program. A. M. was supported by project BFU2016-74975-P.

Cite AsGet BibTex

Delia Garijo, Alberto Márquez, Natalia Rodríguez, and Rodrigo I. Silveira. Computing Optimal Shortcuts for Networks. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.15

Abstract

We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Questions of this type have received considerable attention recently, mostly for discrete variants of the problem. We study a fully continuous setting, where all points on the network and the inserted segment must be taken into account. We present the first results on the computation of optimal shortcuts for general networks in this model, together with several results for networks that are paths, restricted to two types of shortcuts: shortcuts with a fixed orientation and simple shortcuts.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • graph augmentation
  • shortcut
  • diameter
  • geometric graph

Metrics

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

Related Versions

References

  1. S. W. Bae, M. de Berg, O. Cheong, J. Gudmundsson, and C. Levcopoulos. Shortcuts for the Circle. In Proceedings ISAAC 2017, pages 9:1-9:13, 2017. Google Scholar
  2. M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, and P. Sumazin. Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms, 57(2):75-94, 2005. Google Scholar
  3. O. Berkman and U. Vishkin. Recursive Star-Tree Parallel Data Structure. SIAM J. Comput., 22(2):221-242, 1993. Google Scholar
  4. G. S. Brodal and R. Jacob. Dynamic Planar Convex Hull. In Proceedings FOCS '02, pages 617-626, Washington, DC, USA, 2002. IEEE Computer Society. Google Scholar
  5. J. Cáceres, D. Garijo, A. González, A. Márquez, M. L. Puertas, and P. Ribeiro. Shortcut sets for the locus of plane Euclidean networks. Appl. Math. Comp., 334:192-205, 2018. Google Scholar
  6. J. L. De Carufel, C. Grimm, A. Maheshwari, and M. Smid. Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts. In Proceedings SWAT 2016, pages 27:1-27:14, 2016. Google Scholar
  7. J. L. De Carufel, C. Grimm, S. Schirra, and M. Smid. Minimizing the Continuous Diameter when Augmenting a Tree with a Shortcut. In Algorithms and Data Structures. WADS 2017. LNCS 10389, pages 301-312, 2017. Google Scholar
  8. C. E. Chen and R. S. Garfinkel. The generalized diameter of a graph. Networks, 12:335-340, 1982. Google Scholar
  9. M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. Google Scholar
  10. Greg N. Frederickson. Fast Algorithms for Shortest Paths in Planar Graphs, with Applications. SIAM J. Comput., 16(6):1004-1022, December 1987. Google Scholar
  11. K. Y. Fung, T. M. Nicholl, R. E. Tarjan, and C. J. Van Wyk. Simplified linear-time jordan sorting and polygon clipping. Information Processing Letters, 35(2):85-92, 1990. Google Scholar
  12. D. Garijo, A. Márquez, N. Rodríguez, and R. I. Silveira. Computing optimal shortcuts for networks. Preprint, 2018. https://arxiv.org/abs/1807.10093. Google Scholar
  13. P. Hansen, M. Labbé, and B. Nicolas. The continuous center set of a network. Discrete Applied Mathematics, 30:181-195, 1991. Google Scholar
  14. F. Hurtado and C. D. Tóth. Plane Geometric Graph Augmentation: A Generic Perspective. In Pach J. (eds) Thirty Essays on Geometric Graph Theory, pages 327-354. Springer, 2013. Google Scholar
  15. B. Yang. Euclidean Chains and Their Shortcuts. Theor. Comput. Sci., 497:55-67, July 2013. Google Scholar
  16. H. Yang and M. G. H. Bell. Models and algorithms for road network design: a review and some new developments. Transport Reviews, 18(3):257-278, 1998. 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