?? ham.htm
字號:
<title> Jeremy Frank - Hamiltonian Cycle Research Page </title><body background="Temple.gif"><center> <h1> Phase Transitions in Hamiltonian Cycle Problems </h1> </center><blockquote>The <em> Hamiltonian Cycle Problem </em> is to decide whether or not thereis a Hamiltonian Cycle in a given graph. Early results by Erdos and Renyishow that, as N becomes arbitrarily large, a random graph is connectedwith probability 1 if E/N log N > 1/2 and disconnected if E/N log N is< 1/2. Using this result, Posa later showed that, again as N becomes large,a random graph has a Hamiltonian Cycle with probability 1 if E/N log N >cfor some constant. We examined the phase transition for Hamiltonian Cycleand gave evidence supporting the theoretical result; our results suggestthat the constant is smaller than Posa used in his result. We also investigated a probabilistic algorithm designed to find Hamiltonian Cyclesin random graphs in polynomial time in the number of edges. <p>This work is currently being extended to include a more detailed analysisof the computational costs of backtracking search for Hamiltonian Cycleas well as an investigation into the number of Hamiltonian Cycles foundat the phase transition. This work is being done jointly with Ian Gentat the University of Strathclyde, Scotland, and Toby Walsh at IRST in Italy.</blockquote><center> <h2> Related Local Pages </h2> </center><center><A HREF="phases.html"> Introduct?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -