ECCC-Report TR02-021https://eccc.weizmann.ac.il/report/2002/021Comments and Revisions published for TR02-021en-usMon, 15 Apr 2002 16:08:57 +0300
Paper TR02-021
| Space Efficient Algorithms for Directed Series-Parallel Graphs |
Andreas Jakoby,
Maciej Liskiewicz,
RĂ¼diger Reischuk
https://eccc.weizmann.ac.il/report/2002/021The subclass of directed series-parallel graphs plays an important role in
computer science. Whether a given graph is series-parallel is a
well studied problem in algorithmic graph theory, for which fast sequential and
parallel algorithms have been developed in a sequence of papers.
Also methods are known to solve the reachability and the decomposition
problem for series-parallel graphs time efficiently.
However, no dedicated results have been obtained for
the space complexity of these problems when restricted to series-parallel
graphs -- the topic of this paper.
Deterministic algorithms are presented for the recognition, reachability,
decomposition and the path counting problem for series-parallel graphs that use only
logarithmic space. Since for arbitrary directed graphs reachability and path
counting are believed not to be solvable in Logspace the main contribution of
this work are novel deterministic path finding routines that work
correctly in series-parallel graphs, and a characterization of
series-parallel graphs by forbidden subgraphs that can be tested
space-efficiently. The space bounds are best possible,
i.e. the decision problem is shown to be L-complete with respect to
AC^0-reductions. They have also implications for the parallel time complexity
of these problems when restricted to series-parallel graphs.
Finally, we sketch how these results can be generalised to extension of the
series-parallel graph family: to graphs with multiple sources or multiple sinks
and to the class of minimal vertex series-parallel graphs.
Mon, 15 Apr 2002 16:08:57 +0300https://eccc.weizmann.ac.il/report/2002/021