Transitive compaction in parallel via branchings

DOI10.1016/0196-6774(91)90026-UMaRDI QIDQ5750415zbMATH OpenFDO

Authors Phillip B. Gibbons, Vijaya Ramachandran, Danny Soroker, Richard Karp, Robert E. Tarjan

Publication date 1991

Published in Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

CREW PRAMstrongly connected digraphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• High-Probability Parallel Transitive-Closure Algorithms
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
• The Parallel Simplicity of Compaction and Chaining

Cited in

(7)

• Finding strong components using depth-first search
• Removing null branches in a transfinite network
• Efficient parallel algorithms for path problems in directed graphs
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• The Parallel Simplicity of Compaction and Chaining
• Improved processor bounds for parallel algorithms for weighted directed graphs
• scientific article; zbMATH DE number 177853 (Why is no real title available?)

This page was built for publication: Transitive compaction in parallel via branchings

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