An algorithm for finding hamilton cycles in random directed graphs |
| |
| Institution: | 1. Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Republic of Korea;2. Graduate School of Artificial Intelligence, Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Republic of Korea |
| |
| Abstract: | We describe a polynomial (O(n1.5)) time algorithm DHAM for finding hamilton cycles in digraphs. For digraphs chosen uniformly at random from the set of digraphs with vertex set {1, 2, …, n} and m = m(n) edges the limiting probability (as n → ∞) that DHAM finds a hamilton cycle equals the limiting probability that the digraph is hamiltonian. Some applications to random “travelling salesman problems” are discussed. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
