Date
2012
Titre de la collection
Lecture Notes in Computer Science
n° dans la collection
7276/2012
Indexation documentaire
Principes généraux des mathématiques
Subject
vertex cover; low memory; huge graphs; experimental analysis; implementation of algorithms
Titre du colloque
SEA 2012
Date du colloque
06-2012
Ville du colloque
Bordeaux
Pays du colloque
France
Titre de l'ouvrage
Experimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings
Auteur
Klasing, Ralf
Nom de l'éditeur
Springer
Année
2012
ISBN
978-3-642-30849-9
Auteur
Laforest, Christian
Campigotto, Romain
Angel, Eric
Type
Communication / Conférence
Nombre de pages du document
39-50
Résumé en anglais
We present in this paper an experimental study of six heuristics for a well-studied NP-complete graph problem: the vertex cover. These algorithms are adapted to process huge graphs. Indeed, executed on a current laptop computer, they offer reasonable CPU running times (between twenty seconds and eight hours) on graphs for which sizes are between 200 ·106 and 100 ·109 vertices and edges.
We have run algorithms on specific graph families (we propose generators) and also on random power law graphs. Some of these heuristics can produce good solutions. We give here a comparison and an analysis of results obtained on several instances, in terms of quality of solutions and complexity, including running times.
