Space efficient algorithms for directed series-parallel graphs

摘要

The 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.