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 …

We review recent progress in the study of the vertex-cover problem (VC). The VC belongs to
the class of NP-complete graph theoretical problems, which plays a central role in …

In this Letter we study the NP-complete vertex cover problem on finite connectivity random
graphs. When the allowed size of the cover set is decreased, a discontinuous transition in …

In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or
independent sets) of finite-connectivity random graphs is analysed. In every algorithmic step …

The vertex-cover problem is studied for random graphs GN, cN having N vertices and cN
edges. Exact numerical results are obtained by a branch-and-bound algorithm. It is found …

Vertex cover is one of the classical NP-complete problems in theoretical computer science.
A vertex cover of a graph is a subset of vertices such that for each edge at least one of the …

The minimum vertex-cover problems on random α-uniform hypergraphs are studied using
two different approaches, a replica method in statistical mechanics of random systems and a …

A statistical-mechanical study of the effect of constraint relaxation on the minimum vertex
cover problem in Erdős-Rényi random graphs is presented. Using a penalty-method …

We study the vertex-cover problem, which is a nondeterministic polynomial-time hard
optimization problem and a prototypical model exhibiting phase transitions on random …

The mincut graph bisection problem involves partitioning the n vertices of a graph into
disjoint subsets, each containing exactly n/2 vertices, while minimizing the number of “cut” …