Parallei graph algorithms that are efficient on average

AbstractThe 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