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

被引：44

作者：

Weigt, M ^{[1
]}

Hartmann, AK ^{[1
]}

机构：

[1] Univ Gottingen, Inst Theoret Phys, D-37073 Gottingen, Germany

来源：

PHYSICAL REVIEW LETTERS | 2001年 / 86卷 / 08期

关键词：

D O I：

10.1103/PhysRevLett.86.1658

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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.

引用

页码：1658 / 1661

页数：4

共 14 条

[1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2] Bollobas B, 1985, RANDOM GRAPHS
[3] PROBABILISTIC ANALYSIS OF 2 HEURISTICS FOR THE 3-SATISFIABILITY PROBLEM
CHAO, MT
FRANCO, J
[J]. SIAM JOURNAL ON COMPUTING, 1986, 15 (04) : 1106 - 1118
[4] Trajectories in phase diagrams, growth processes, and computational complexity: How search algorithms solve the 3-satisfiability problem
Cocco, S
Monasson, R
[J]. PHYSICAL REVIEW LETTERS, 2001, 86 (08) : 1654 - 1657
[5] DUBOIS O, IN PRESS THEOR COMPU
[6] ON THE INDEPENDENCE NUMBER OF RANDOM GRAPHS
FRIEZE, AM
[J]. DISCRETE MATHEMATICS, 1990, 81 (02) : 171 - 175
[7] INDEPENDENT SETS IN RANDOM SPARSE GRAPHS
GAZMURI, PG
[J]. NETWORKS, 1984, 14 (03) : 367 - 377
[8] HOGG T, 1996, ARTIFICIAL INTELLIGE, V81
[9] BRANCH-AND-BOUND METHODS - A SURVEY
LAWLER, EL
WOOD, DE
[J]. OPERATIONS RESEARCH, 1966, 14 (04) : 699 - +
[10] Phase transition in the number partitioning problem
Mertens, S
[J]. PHYSICAL REVIEW LETTERS, 1998, 81 (20) : 4281 - 4284

← 1 2 →