Kernels for the vertex cover problem on the preferred attachment model

Josep Díaz, Jordi Petit, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We examine the behavior of two kernelization techniques for the vertex cover problem viewed as preprocessing algorithms. Specifically, we deal with the kernelization algorithms of Buss and of Nemhauser & Trotter. Our evaluation is applied to random graphs generated under the preferred attachment model, which is usually met in real word applications such as web graphs and others. Our experiments indicate that, in this model, both kernelization algorithms (and, specially, the Nemhauser & Trotter algorithm) reduce considerably the input size of the problem and can serve as very good preprocessing algorithms for vertex cover, on the preferential attachment graphs.

Original languageEnglish (US)
Title of host publicationExperimental Algorithms - 5th International Workshop, WEA 2006, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540345973, 9783540345978
StatePublished - 2006
Event5th International Workshop on Experimental Algorithms, WEA 2006 - Cala Galdana, Menorca, Spain
Duration: May 24 2006May 27 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4007 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th International Workshop on Experimental Algorithms, WEA 2006
CityCala Galdana, Menorca

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Kernels for the vertex cover problem on the preferred attachment model'. Together they form a unique fingerprint.

Cite this