Show simple item record

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

dc.contributor.authorLaforest, Christian
HAL ID: 171365
dc.contributor.authorCampigotto, Romain
dc.contributor.authorAngel, Eric
dc.date.accessioned2012-07-16T12:16:20Z
dc.date.available2012-07-16T12:16:20Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9753
dc.language.isoenen
dc.subjectvertex coveren
dc.subjectlow memoryen
dc.subjecthuge graphsen
dc.subjectexperimental analysisen
dc.subjectimplementation of algorithmsen
dc.subject.ddc511en
dc.titleImplementation and Comparison of Heuristics for the Vertex Cover Problem on Huge Graphsen
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherLIMOS, CNRS UMR 6158, Université Blaise Pascal;France
dc.contributor.editoruniversityotherLaboratoire IBISC, EA 4526, Université d’Évry-Val d’Essonne, IBGBI;France
dc.description.abstractenWe 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.en
dc.identifier.citationpages39-50en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber7276/2012
dc.relation.ispartoftitleExperimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedingsen
dc.relation.ispartofeditorKlasing, Ralf
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofdate2012
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-30850-5en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-642-30849-9en
dc.relation.conftitleSEA 2012en
dc.relation.confdate2012-06
dc.relation.confcityBordeauxen
dc.relation.confcountryFranceen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-30850-5_5


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record