License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6185
URL: http://drops.dagstuhl.de/opus/volltexte/2006/618/

Jakoby, Andreas ; Tantau, Till

Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space

pdf-format:
Dokument 1.pdf (161 KB)


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:DSP:2006:618,
  author =	{Andreas Jakoby and Till Tantau},
  title =	{Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space},
  booktitle =	{Complexity of Boolean Functions},
  year =	{2006},
  editor =	{Matthias Krause and Pavel Pudl{\'a}k and R{\"u}diger Reischuk and Dieter van Melkebeek},
  number =	{06111},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/618},
  annote =	{Keywords: Series-parallel graphs, shortest path, logspace}
}

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


DROPS-Home | Fulltext Search | Imprint Published by LZI