Document Open Access Logo

Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space

Authors Andreas Jakoby, Till Tantau

PDF

File

Thumbnail PDF
PDF
DagSemProc.06111.6.pdf
  • Filesize: 160 kB
  • 9 pages

Document Identifiers

Subject Classification

Keywords
  • Series-parallel graphs
  • shortest path
  • logspace

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Andreas Jakoby and Till Tantau. Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006) https://doi.org/10.4230/DagSemProc.06111.6

Author Details

Andreas Jakoby
Till Tantau
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact