Parallel recognition and decomposition of two terminal series parallel graphs

DOI10.1016/0890-5401(87)90061-7zbMATH Open0636.68090OpenAlexW2030429378MaRDI QIDQ1098313FDOQ1098313

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)