Mesoscopic Behavior in Biological and Physical Systems, August 28-September 4, 2006, Budapest, Hungary
|
Hamiltonian cycles in sparse random graphs Tom Bohman, Department of Mathematics Carnegie Mellon University Abstract We discuss an approach to finding Hamiltonian cycles in sparse random graphs that was developed to prove that the sparse random graph known as 3-out has a Hamiltonian cycle with high probability. The methods introduced have the potential to establish Hamiltonicity for several other sparse random graph models. We also note connections with the Karp-Sipser algorithm (which is a randomized algorithm for finding a matching in a graph). |
|
Go back to Workshop front page.
|