Parallel graph algorithms that are efficient on average | IEEE Conference Publication | IEEE Xplore

Parallel graph algorithms that are efficient on average

Publisher: IEEE

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 more

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
Publisher: IEEE
Conference Location: Los Angeles, CA, USA

References

References is not available for this document.