Clustering analysis of the ground-state structure of the vertex-cover problem

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 two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one obs...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2004-12, Vol.70 (6 Pt 2), p.066120-066120, Article 066120
Main Authors: Barthel, Wolfgang, Hartmann, Alexander K
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c
ISSN:1539-3755
1550-2376
DOI:10.1103/physreve.70.066120