Kernelization of the 3-path vertex cover problem

DOI10.1016/j.disc.2015.12.006zbMath1334.05069OpenAlexW2275951435MaRDI QIDQ279214

Ingo Schiermeyer, Christoph Brause

Publication date: 27 April 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2015.12.006

zbMATH Keywords

vertex coverkernelization\(k\)-path vertex covercrown reduction

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items (2)

The geodesic-transversal problem ⋮ 3-path vertex cover and dissociation number of hexagonal graphs

Cites Work

• Unnamed Item
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A generalization of Nemhauser and Trotter's local optimization theorem
• Looking at the stars
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• The vertex cover \(P_3\) problem in cubic graphs
• Vertex packings: Structural properties and algorithms

This page was built for publication: Kernelization of the 3-path vertex cover problem