Parallel graph algorithms that are efficients on average

DOI10.1016/0890-5401(89)90035-7MaRDI QIDQ1825648zbMATH OpenOpenAlexFDO

Authors Don Coppersmith, Prabhakar Raghavan, Martin Tompa

Publication date 1989

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(89)90035-7

zbMATH Keywords

average case analysisCRCW PRAMmodel of computationparallel algorithmsrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 219240
• A fast parallel algorithm for the maximal independent set problem
• A processor efficient MIS algorithm on random graphs
• Removing randomness in parallel computation without a processor penalty
• scientific article; zbMATH DE number 17674

Cites work

• A taxonomy of problems with fast parallel algorithms
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 3945879 (Why is no real title available?)
• scientific article; zbMATH DE number 3638844 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Parallel algorithms for finding Hamilton cycles in random graphs
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• The chromatic number of random graphs

Cited in

(15)

• Expected parallel time and sequential space complexity of graph and digraph problems
• Efficient parallel algorithms for graph problems
• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 4205985 (Why is no real title available?)
• Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• scientific article; zbMATH DE number 3972201 (Why is no real title available?)
• scientific article; zbMATH DE number 4033068 (Why is no real title available?)
• scientific article; zbMATH DE number 1215999 (Why is no real title available?)
• scientific article; zbMATH DE number 219240 (Why is no real title available?)
• A measure for the lexicographically first maximal independent set problem and its limits
• A distributed algorithm for finding Hamiltonian cycles in random graphs in O( n) time
• Coloring k-colorable graphs in constant expected parallel time
• Distributed MIS in O(log log n) Awake Complexity
• Distributed MIS in O( n) awake complexity

This page was built for publication: Parallel graph algorithms that are efficients on average

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