Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
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.
Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory
Thomas M. Cover
IEEE Trans. Inf. Theory
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021