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 m...View moreMetadata
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.
Date of Conference: 12-14 October 1987
Date Added to IEEE Xplore: 18 July 2008
Print ISBN:0-8186-0807-2
Print ISSN: 0272-5428