Parallel graph algorithms that are efficients on average
From MaRDI portal
Publication:1825648
DOI10.1016/0890-5401(89)90035-7zbMath0684.68049OpenAlexW2151636922MaRDI QIDQ1825648
Don Coppersmith, Martin Tompa, Prabhakar Raghavan
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
Coloring k-colorable graphs in constant expected parallel time ⋮ Distributed MIS in O(log log n) Awake Complexity ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph ⋮ A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time ⋮ A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Parallel algorithms for finding Hamilton cycles in random graphs
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
- A taxonomy of problems with fast parallel algorithms
- The chromatic number of random graphs
This page was built for publication: Parallel graph algorithms that are efficients on average
