An algorithm for finding hamilton paths and cycles in random graphs |
| |
| Authors: | B Bollobás T I Fenner A M Frieze |
| |
| Institution: | (1) Department of Pure Mathematics, University of Cambridge, Cambridge, England;(2) Department of Mathematics, LSU, Baton Rouge, LA, USA;(3) Department of Computer Science Birkbeck College, University of London, England;(4) Department of Computer Science Queen Mary College, University of London, England;(5) Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, USA |
| |
| Abstract: | This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph
its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected
time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending
to 1, asn tends to ∞.
Various modifications of HAM are shown to solve several Hamilton path problems.
Supported by NSF Grant MCS 810 4854. |
| |
| Keywords: | 05 C 45 68 E 10 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
