Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
DY: Fachverband Dynamik und Statistische Physik
DY 40: Posters II
DY 40.41: Poster
Donnerstag, 17. März 2011, 17:00–19:00, P3
Cutting-Plane Approach for Vertex Covering of Random Graphs — •Timo Dewenter and Alexander K. Hartmann — Institut für Physik, Universität Oldenburg, 26111 Oldenburg
The NP-complete vertex cover problem (VC) on Erdős-Rényi (ER) random graphs with finite connectivity c is well studied [1]. Within numerical simulations, usually the minimum-size cover is calculated via branch-and-bound algorithms.
Here, we apply the translation of VC to a linear programming problem (LP), where the nodes of the graph are represented by variables xi ∈ [0,1]. Each edge {j,k} of the graph corresponds to a constraint xj + xk ≥ 1. The simplex algorithm is used to solve this LP, but for larger c less solutions of the desired form xi ∈ {0,1} are found. So we use two heuristics to obtain better results. First, a node-heuristic is implemented, which generates an upper bound of the minimum cover. Further, a cutting plane approach is used, that adds constraints to the LP based on loops in the graph with odd length leading to exact solutions or lower bounds. We study the behaviour of these algorithms for ER random graphs as a function of c. After performing a statistical analysis [2] for different system sizes, we compare with the phase diagram for the critical fraction xc of covered vertices.
M. Weigth and A.K. Hartmann: Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs, Phys. Rev. Letters 84, 26 (2000)
A.K. Hartmann: Practical Guide to Computer Simulations, World-Scientific, 2009