The recognition of series parallel digraphs

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

doi:https://doi.org/10.1145/800135.804393

The recognition of series parallel digraphs

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

Research output: Contribution to journal › Conference article › peer-review

118 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 language	American English
Pages (from-to)	1-12
Number of pages	12
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/800135.804393
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

ASJC Scopus subject areas

Software

Access to Document

https://doi.org/10.1145/800135.804393

Cite this

@article{c74bce82a4d34a2389e89b903d45f796,

title = "The recognition of series parallel digraphs",

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.",

author = "Jacobo Valdes and Tarjan, {Robert E.} and Lawler, {Eugene L.}",

note = "Funding Information: The remainder of this paper is divided into four sections. The first one provides the definitions and elementary facts needed to understand the recognition procedure. In the second, the procedure itself is first outlined and shown correct, and an implemen- * Work supported by NSF Grant MCS-75-22870 and ONR Grant N00014-76-C-0688. {"}t-Work supported by NSF Granl M('S-76-17605. Publisher Copyright: {\textcopyright} 1979 Association for Computing Machinery. All rights reserved.; 11th Annual ACM Symposium on Theory of Computing, STOC 1979 ; Conference date: 30-04-1979 Through 02-05-1979",

year = "1979",

month = apr,

day = "30",

doi = "https://doi.org/10.1145/800135.804393",

language = "American English",

pages = "1--12",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - The recognition of series parallel digraphs

AU - Valdes, Jacobo

AU - Tarjan, Robert E.

AU - Lawler, Eugene L.

N1 - Funding Information: The remainder of this paper is divided into four sections. The first one provides the definitions and elementary facts needed to understand the recognition procedure. In the second, the procedure itself is first outlined and shown correct, and an implemen- * Work supported by NSF Grant MCS-75-22870 and ONR Grant N00014-76-C-0688. "t-Work supported by NSF Granl M('S-76-17605. Publisher Copyright: © 1979 Association for Computing Machinery. All rights reserved.

PY - 1979/4/30

Y1 - 1979/4/30

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

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

UR - http://www.scopus.com/inward/record.url?scp=85009154075&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85009154075&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/800135.804393

DO - https://doi.org/10.1145/800135.804393

M3 - Conference article

SN - 0737-8017

SP - 1

EP - 12

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 11th Annual ACM Symposium on Theory of Computing, STOC 1979

Y2 - 30 April 1979 through 2 May 1979

ER -

The recognition of series parallel digraphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this