Kernelization for cycle transversal problems

DOI10.1016/j.dam.2011.12.024zbMath1242.05142OpenAlexW1977629138MaRDI QIDQ423937

Ge Xia, Yong Zhang

Publication date: 30 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.dam.2011.12.024

zbMATH Keywords

planar graphskernelizationcycle transversal

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (3)

A survey of parameterized algorithms and the complexity of edge modification ⋮ Fractals for Kernelization Lower Bounds ⋮ Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal

Cites Work

• Unnamed Item
• On the small cycle transversal of planar graphs
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• A kernelization algorithm for \(d\)-hitting set
• On the chromatic number of triangle-free graphs of large minimum degree
• On a conjecture of Tuza about packing and covering of triangles
• On the number of edges of quadrilateral-free graphs
• On the chromatic number of pentagon-free graphs of large minimum degree
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• On the Turán number for the hexagon
• Bipartite subgraphs
• On Generating Triangle-Free Graphs
• Hypergraphs with no odd cycle of given length
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Which Codes Have$4$-Cycle-Free Tanner Graphs?
• M-degrees of quadrangle-free planar graphs
• Adapted list coloring of planar graphs
• Node-and edge-deletion NP-complete problems
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• A Note on Bipartite Graphs Without 2 k -Cycles
• Approximating Maximum Subgraphs without Short Cycles

This page was built for publication: Kernelization for cycle transversal problems