Kernels for the Vertex Cover Problem on the Preferred Attachment Model

DOI10.1007/11764298_21MaRDI QIDQ5307546zbMATH OpenOpenAlexFDO

Authors Jordi Petit, Dimitrios M. Thilikos, J. Díaz

Publication date 14 September 2007

Published in Experimental Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11764298_21

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Crown structures for vertex cover kernelization
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• A kernel of order 2k-c k for vertex cover
• A kernel of order \(2k - c\) for Vertex Cover

Cited in

(2)

• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}

This page was built for publication: Kernels for the Vertex Cover Problem on the Preferred Attachment Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5307546)