Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs

DOI10.1006/JAGM.1993.1017zbMATH Open0768.68155OpenAlexW2081804932MaRDI QIDQ4696644FDOQ4696644

Authors: Philip N. Klein 

Publication date: 29 June 1993

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

Full work available at URL: https://doi.org/10.1006/jagm.1993.1017

Recommendations

• scientific article; zbMATH DE number 4117855
• On the parallel complexity of digraph reachability
• Nearly work-efficient parallel algorithm for digraph reachability
• Nearly work-efficient parallel algorithm for digraph reachability
• Efficient parallel algorithms for path problems in directed graphs

zbMATH Keywords

hybrid algorithmreachabilitysparse graphsdirected graphparallelizationpreprocessing

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10)

Cited In (5)

• Parallel processing of graph reachability in databases
• Nearly work-efficient parallel algorithm for digraph reachability
• Map-Reduce process algebra: a formalism to describe directed acyclic graph task-based jobs in parallel environments
• Nearly work-efficient parallel algorithm for digraph reachability
• On the time-space complexity of reachability queries for preprocessed graphs

This page was built for publication: Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs

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