License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.6
URN: urn:nbn:de:0030-drops-6185
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/618/
Go to the corresponding Portal

Jakoby, Andreas ; Tantau, Till

Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space

pdf-format:
06111.TantauTill.Paper.618.pdf (0.2 MB)

Abstract

Series-parallel graphs, which are built by repeatedly applying
series or parallel composition operations to paths, play an
important role in computer science as they model the flow of
information in many types of programs. For directed series-parallel
graphs, we study the problem of finding a shortest path between two
given vertices. Our main result is that we can find such a path in
logarithmic space, which shows that the distance problem for
series-parallel graphs is L-complete. Previously, it was known
that one can compute some path in logarithmic space; but for
other graph types, like undirected graphs or tournament graphs,
constructing some path between given vertices is possible in
logarithmic space while constructing a shortest path is
NL-complete.


BibTeX - Entry

@InProceedings{jakoby_et_al:DagSemProc.06111.6,
  author =	{Jakoby, Andreas and Tantau, Till},
  title =	{{Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/618},
  URN =		{urn:nbn:de:0030-drops-6185},
  doi =		{10.4230/DagSemProc.06111.6},
  annote =	{Keywords: Series-parallel graphs, shortest path, logspace}
}

Keywords: Series-parallel graphs, shortest path, logspace
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 30.11.2006

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