License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.15
URN: urn:nbn:de:0030-drops-99634
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9963/
Go to the corresponding LIPIcs Volume Portal

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

Computing Optimal Shortcuts for Networks

pdf-format:
LIPIcs-ISAAC-2018-15.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{garijo_et_al:LIPIcs:2018:9963,
  author =	{Delia Garijo and Alberto M{\'a}rquez and Natalia Rodr{\'i}guez and Rodrigo I. Silveira},
  title =	{{Computing Optimal Shortcuts for Networks}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{15:1--15:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9963},
  URN =		{urn:nbn:de:0030-drops-99634},
  doi =		{10.4230/LIPIcs.ISAAC.2018.15},
  annote =	{Keywords: graph augmentation, shortcut, diameter, geometric graph}
}

Keywords: graph augmentation, shortcut, diameter, geometric graph
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI