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.SWAT.2016.27
URN: urn:nbn:de:0030-drops-60492
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6049/
Go to the corresponding LIPIcs Volume Portal

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

Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts

pdf-format:
LIPIcs-SWAT-2016-27.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{decarufel_et_al:LIPIcs:2016:6049,
  author =	{Jean-Lou De Carufel and Carsten Grimm and Anil Maheshwari and Michiel Smid},
  title =	{{Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6049},
  URN =		{urn:nbn:de:0030-drops-60492},
  doi =		{10.4230/LIPIcs.SWAT.2016.27},
  annote =	{Keywords: Network Augmentation, Shortcuts, Diameter, Paths, Cycles}
}

Keywords: Network Augmentation, Shortcuts, Diameter, Paths, Cycles
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

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