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

DOI10.1006/JAGM.1993.1017MaRDI QIDQ4696644zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

hybrid algorithmreachabilitysparse graphsdirected graphparallelizationpreprocessing

Mathematics Subject Classification ID

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

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

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)