Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs

Details Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs

2000-09-27

arxiv.org/abs/cond-mat/0009417v2

Phys. Rev. Lett. 86, 1658 (2001)

Physics

Condensed Matter

Disordered Systems and Neural Networks

4 pages, 2 figures, to appear in Phys. Rev. Lett

Scientific paper

10.1103/PhysRevLett.86.1658

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.

Affiliated with

Also associated with

No associations

Rating

Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-631489