we present an algorithm that recognizes the class of General Series Parallel digraphs and runs in time proportional to the size of its input. To perform this recognition task it is necessary to compute the transitive reduction and transitive closure of any General Series Parallel digraph. Our analysis is based on the relationship between General Series Parallel digraphs and a class of well known models of electrical networks.
|Original language||English (US)|
|Number of pages||12|
|Journal||Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - Apr 30 1979|
|Event||11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States|
Duration: Apr 30 1979 → May 2 1979
All Science Journal Classification (ASJC) codes