On the small cycle transversal of planar graphs
From MaRDI portal
Publication:551170
DOI10.1016/J.TCS.2011.02.040zbMath1217.68114OpenAlexW2020842595MaRDI QIDQ551170
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
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (5)
Kernelization for cycle transversal problems ⋮ Fractals for Kernelization Lower Bounds ⋮ On the Small Cycle Transversal of Planar Graphs ⋮ New kernels for several problems on planar graphs ⋮ Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding next-to-shortest paths in a graph
- Decomposing a planar graph with girth 9 into a forest and a matching
- 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
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- A Linear Kernel for Planar Feedback Vertex Set
- On Problems without Polynomial Kernels (Extended Abstract)
- Kernelization for Cycle Transversal Problems
- Polynomial-time data reduction for dominating set
- A Cubic Kernel for Feedback Vertex 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
This page was built for publication: On the small cycle transversal of planar graphs
