Kernelization for cycle transversal problems

DOI10.1016/J.DAM.2011.12.024zbMATH Open1242.05142OpenAlexW1977629138MaRDI QIDQ423937FDOQ423937

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

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

zbMATH Keywords

planar graphskernelizationcycle transversal

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Kernelization for cycle transversal problems
• On the small cycle transversal of planar graphs
• Fractals for Kernelization Lower Bounds
• A survey of parameterized algorithms and the complexity of edge modification
• On the small cycle transversal of planar graphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal

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)