Publication
Information and Computation
Paper

Parallei graph algorithms that are efficient on average

View publication

Abstract

The following three problems concerning random graphs can be solved in (log n)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. © 1989.

Date

01 Jan 1989

Publication

Information and Computation

Authors

Topics

Share