Kernelization for cycle transversal problems

DOI10.1016/J.DAM.2011.12.024MaRDI QIDQ423937zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Kernelization for cycle transversal problems
• On the small cycle transversal of planar graphs
• On the small cycle transversal of planar graphs
• New kernels for several problems on planar graphs
• Improved kernels for several problems on planar graphs

Cites work

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

Cited in

(13)

• Kernelization for cycle transversal problems
• On the small cycle transversal of planar graphs
• On the hardness of losing width
• A survey of parameterized algorithms and the complexity of edge modification
• On the small cycle transversal of planar graphs
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
• Exploring the kernelization borders for hitting cycles
• New kernels for several problems on planar graphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Fractals for kernelization lower bounds
• Cycle transversals in bounded degree graphs
• Improved kernels for several problems on planar graphs
• Cycle transversals in bounded degree graphs

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

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