On the small cycle transversal of planar graphs

DOI10.1016/J.TCS.2011.02.040MaRDI QIDQ551170zbMATH OpenOpenAlexFDO

Authors Ge Xia, Yong Zhang

Publication date 14 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.02.040

zbMATH Keywords

cycle transversalkernelizationparameterized complexityplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

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

Cites work

• (Meta) Kernelization
• A Cubic Kernel for Feedback Vertex Set
• A Linear Kernel for Planar Feedback Vertex Set
• A quadratic kernel for feedback vertex set
• Approximating Maximum Subgraphs without Short Cycles
• Decomposing a planar graph with girth 9 into a forest and a matching
• Equitable list colorings of planar graphs without short cycles
• Finding next-to-shortest paths in a graph
• Generating random graphs with large girth
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1532269 (Why is no real title available?)
• scientific article; zbMATH DE number 2229025 (Why is no real title available?)
• Kernelization for cycle transversal problems
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Node-and edge-deletion NP-complete problems
• On generating triangle-free graphs
• On Problems without Polynomial Kernels (Extended Abstract)
• Polynomial-time data reduction for dominating set
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Star coloring high girth planar graphs
• The size of bipartite graphs with a given girth
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

Cited in

(7)

• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• New kernels for several problems on planar graphs
• On the small cycle transversal of planar graphs
• Kernelization for cycle transversal problems
• Kernelization for cycle transversal problems
• Fractals for kernelization lower bounds
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs

This page was built for publication: On the small cycle transversal of planar graphs

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