Finding Hamilton cycles in sparse random graphs (Q1080865)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Finding Hamilton cycles in sparse random graphs |
scientific article |
Statements
Finding Hamilton cycles in sparse random graphs (English)
0 references
1988
0 references
We describe a polynomial time \((O(n^ 3\log n))\) algorithm which has a high probability of finding Hamilton cycles in 2 classes of random graph which have constant average degree: the m-out model and the random regular graph model. We also show how the algorithm can be used to find a large cycle in a sparse random graph.
0 references
polynomial time algorithm
0 references
Hamilton cycles
0 references
random graph
0 references
0 references
0 references
