Transitive compaction in parallel via branchings

DOI10.1016/0196-6774(91)90026-UzbMATH Open0718.68058MaRDI QIDQ5750415FDOQ5750415

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

Publication date: 1991

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

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

zbMATH Keywords

CREW PRAMstrongly connected digraphs

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• Improved processor bounds for parallel algorithms for weighted directed graphs

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)