Abstract
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) |
---|---|
Pages (from-to) | 1-12 |
Number of pages | 12 |
Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - Apr 30 1979 |
Externally published | Yes |
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
- Software