• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Implementation and Comparison of Heuristics for the Vertex Cover Problem on Huge Graphs

Laforest, Christian; Campigotto, Romain; Angel, Eric (2012), Implementation and Comparison of Heuristics for the Vertex Cover Problem on Huge Graphs, in Klasing, Ralf, Experimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings, Springer, p. 39-50. http://dx.doi.org/10.1007/978-3-642-30850-5_5

Type
Communication / Conférence
Date
2012
Conference title
SEA 2012
Conference date
2012-06
Conference city
Bordeaux
Conference country
France
Book title
Experimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings
Book author
Klasing, Ralf
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
7276/2012
ISBN
978-3-642-30849-9
Pages
39-50
Publication identifier
http://dx.doi.org/10.1007/978-3-642-30850-5_5
Metadata
Show full item record
Author(s)
Laforest, Christian
Campigotto, Romain
Angel, Eric
Abstract (EN)
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.
Subjects / Keywords
vertex cover; low memory; huge graphs; experimental analysis; implementation of algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    A New Lower Bound on the Independence Number of Graphs 
    Angel, Eric; Campigotto, Romain; Laforest, Christian (2013) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence
  • Thumbnail
    Extension and its price for the connected vertex cover problem 
    Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo