The recognition of series parallel digraphs

Jacobo Valdes, Robert E. Tarjan, Eugene L. Lawler

Research output: Contribution to journalConference article

112 Scopus citations

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 languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Apr 30 1979
Externally publishedYes
Event11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States
Duration: Apr 30 1979May 2 1979

All Science Journal Classification (ASJC) codes

  • Software

Cite this