Phys. Rev. Lett. 86, 1658–1661 (2001)Typical Solution Time for a Vertex-Covering Algorithm on Finite-Connectivity Random GraphsReceived 27 September 2000; published in the issue dated 19 February 2001 We analytically describe the typical solution time needed by a backtracking algorithm to solve the vertex-cover problem on finite-connectivity random graphs. We find two different transitions: The first one is algorithm dependent and marks the dynamical transition from linear to exponential solution times. The second one gives the maximum computational complexity, and is found exactly at the threshold where the system undergoes an algorithm-independent phase transition in its solvability. Analytical results are corroborated by numerical simulations. © 2001 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevLett.86.1658
DOI:
10.1103/PhysRevLett.86.1658
PACS:
89.20.Ff, 02.70.-c, 05.20.-y
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.