Parallei graph algorithms that are efficient on average

The following three problems concerning random graphs can be solved in (logn) O(1)expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

Authors

• Don Coppersmith
• Prabhakar Raghavan
• Martin Tompa

Keywords

No keywords are indexed for this paper.