Parallel recognition and decomposition of two terminal series parallel graphs

DOI10.1016/0890-5401(87)90061-7zbMath0636.68090OpenAlexW2030429378MaRDI QIDQ1098313

Yaacov Yesha, Xin He

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90061-7

zbMATH Keywords

parallel algorithmacyclic graphdecomposition treetwo terminal series parallel graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs ⋮ Parallel recognition of complement reducible graphs and cotree construction ⋮ Planar orientations with low out-degree and compaction of adjacency matrices ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ Parallel recognition of series-parallel graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling ⋮ A note on the tour problems in two-terminal series-parallel graphs

Cites Work

• Topology of series-parallel networks
• Linear-time computability of combinatorial problems on series-parallel graphs
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints