Conference paper
Greedy Local Search and Vertex Cover in Sparse Random Graphs
Recently, various randomized search heuristics have been studied for the solution of the minimum vertex cover problem, in particular for sparse random instances according to the G(n, c/n) model, where c > 0 is a constant. Methods from statistical physics suggest that the problem is easy if c
Subsequently, theoretical supplements are given to experimental studies of search heuristics on random graphs. For c <1, a greedy and randomized local-search heuristic finds an optimal cover in polynomial time with a probability arbitrarily close to 1. This behavior relies on the absence of a giant component.
As an additional insight into the randomized search, it is shown that the heuristic fails badly also on graphs consisting of a single tree component of maximum degree 3.
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2009 |
Pages: | 410-419 |
Proceedings: | 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009)Annual Conference on Theory and Applications of Models of Computation |
Series: | Lecture Notes in Computer Science |
Journal subtitle: | 6th Annual Conference, Tamc 2009, Changsha, China, May 18-22, 2009. Proceedings |
ISBN: | 364202016X , 364202016x , 3642020178 , 9783642020162 and 9783642020179 |
ISSN: | 03029743 |
Types: | Conference paper |
DOI: | 10.1007/978-3-642-02017-9_43 |
ORCIDs: | Witt, Carsten |