2026-07-23T04:50:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9963 2024-03-06T10:45:13Z ddc:004 open_access

Computing Optimal Shortcuts for Networks Garijo, Delia Márquez, Alberto Rodríguez, Natalia Silveira, Rodrigo I. graph augmentation shortcut diameter geometric graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Delia Garijo and Alberto Márquez and Natalia Rodríguez and Rodrigo I. Silveira 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.15 urn:nbn:de:0030-drops-99634 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode