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

Agarwal, Udit ; Ramachandran, Vijaya

Finding k Simple Shortest Paths and Cycles

pdf-format:
LIPIcs-ISAAC-2016-8.pdf (0.5 MB)

Abstract

We present algorithms and techniques for several problems related to finding multiple simple shortest paths and cycles in a graph. Our main result is a new algorithm for finding k simple shortest paths for all pairs of vertices in a weighted directed graph G = (V, E). For k = 2 our algorithm runs in O(mn + n^2 log n) time where m and n are the number of edges and vertices in G. For k = 3 our algorithm runs in O(mn^2 + n^3 log n) time, which is almost a factor of n faster than the best previous algorithm.

Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the 'detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles.

We present new algorithms for generating simple cycles and simple paths in G in non-decreasing order of their weight. The algorithm for generating simple paths is much faster,and uses another variant of path extensions.

BibTeX - Entry

@InProceedings{agarwal_et_al:LIPIcs:2016:6783,
  author =	{Udit Agarwal and Vijaya Ramachandran},
  title =	{{Finding k Simple Shortest Paths and Cycles}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{8:1--8:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6783},
  URN =		{urn:nbn:de:0030-drops-67830},
  doi =		{10.4230/LIPIcs.ISAAC.2016.8},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, k Simple Shortest Paths, Enumerat- ing Simple Cycles, Enumerating Simple Paths}
}

Keywords: Graph Algorithms, Shortest Paths, k Simple Shortest Paths, Enumerat- ing Simple Cycles, Enumerating Simple Paths
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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