Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space

Complexity of Boolean Functions

计算机科学;物理学;物理学

Andreas Jakoby

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/618/pdf/06111.TantauTill.Paper.618.pdf
PID  :  6444

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Series-parallel graphs, which are built by repeatedly applying series or parallel compo- sition 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