Jakoby, Andreas ;
Tantau, Till
Computing Shortest Paths in SeriesParallel Graphs in Logarithmic Space
Abstract
Seriesparallel 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 seriesparallel
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
seriesparallel graphs is Lcomplete. 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
NLcomplete.
BibTeX  Entry
@InProceedings{jakoby_et_al:DSP:2006:618,
author = {Andreas Jakoby and Till Tantau},
title = {Computing Shortest Paths in SeriesParallel 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 = {18624405},
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: Seriesparallel graphs, shortest path, logspace}
}
Keywords: 

Seriesparallel graphs, shortest path, logspace 
Seminar: 

06111  Complexity of Boolean Functions

Issue date: 

2006 
Date of publication: 

30.11.2006 