Parallel recognition and decomposition of two terminal series parallel graphs

DOI10.1016/0890-5401(87)90061-7MaRDI QIDQ1098313zbMATH OpenOpenAlexFDO

Authors Xin He, Yaacov Yesha

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)

Recommendations

• Parallel algorithms for series parallel graphs
• Publication:4489178
• scientific article; zbMATH DE number 1107730
• Parallel recognition of series-parallel graphs
• Computational Science - ICCS 2004

Cites work

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

Cited in

(12)

• Monotonicity of equilibria in nonatomic congestion games
• Binary tree algebraic computation and parallel algorithms for simple graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• Parallel recognition of series-parallel graphs
• scientific article; zbMATH DE number 1472126 (Why is no real title available?)
• An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs
• Parallel recognition of complement reducible graphs and cotree construction
• Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling
• Efficient parallel recognition of some circular arc graphs. II
• A note on the tour problems in two-terminal series-parallel graphs
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Efficient parallel recognition of some circular arc graphs. I

This page was built for publication: Parallel recognition and decomposition of two terminal series parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098313)