Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
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.
Sprache
Englisch
Identifikatoren
ISSN: 0031-9007
eISSN: 1079-7114
DOI: 10.1103/physrevlett.86.1658
Titel-ID: cdi_proquest_miscellaneous_77035115
Format
–
Weiterführende Literatur
Empfehlungen zum selben Thema automatisch vorgeschlagen von bX