On the Small Cycle Transversal of Planar Graphs

DOI10.1007/978-3-642-16926-7_12zbMath1310.05205OpenAlexW2164798767MaRDI QIDQ3057617

Ge Xia, Yong Zhang

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_12

zbMATH Keywords

planar graphsparameterized complexitykernelizationcycle transversal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• On the small cycle transversal of planar graphs
• Finding next-to-shortest paths in a graph
• Equitable list colorings of planar graphs without short cycles
• 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
• Maximum cuts and judicious partitions in graphs without short cycles
• The size of bipartite graphs with a given girth
• On Generating Triangle-Free Graphs
• Kernelization for Cycle Transversal Problems
• Polynomial-time data reduction for dominating set
• (Meta) Kernelization
• Node-and edge-deletion NP-complete problems
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Approximating Maximum Subgraphs without Short Cycles