|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs | | Martin Weigt
; Alexander K. Hartmann
; | | Date: |
27 Sep 2000 | | Journal: | Phys. Rev. Lett. 86, 1658 (2001) | | Subject: | Disordered Systems and Neural Networks; Statistical Mechanics; Computational Complexity | cond-mat.dis-nn cond-mat.stat-mech cs.CC | | Abstract: | In this letter, 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. | | Source: | arXiv, cond-mat/0009417 | | Other source: | [GID 792192] pmid11290217 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER