New kernels for several problems on planar graphs
From MaRDI portal
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Recommendations
Cites work
- scientific article; zbMATH DE number 434499 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- Algorithms – ESA 2004
- Approximability results for the maximum and minimum maximal induced matching problems
- Approximating Maximum Subgraphs without Short Cycles
- Approximating maximum agreement forest on multiple binary trees
- Approximation and Online Algorithms
- Edge-disjoint packing of stars and cycles
- Equitable list colorings of planar graphs without short cycles
- Finding a maximum induced matching in weakly chordal graphs
- Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
- Improved PTAS for the constrained \(k\)-means problem
- Improved induced matchings in sparse graphs
- Induced matchings
- Induced matchings in intersection graphs.
- Irredundancy in circular arc graphs
- Kernelization for cycle transversal problems
- Kernelization. Theory of parameterized preprocessing
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Matching theory
- Maximum cuts and judicious partitions in graphs without short cycles
- NP-completeness of some generalizations of the maximum matching problem
- New results on induced matchings
- Node-and edge-deletion NP-complete problems
- On a conjecture of Tuza about packing and covering of triangles
- On generating triangle-free graphs
- On maximum induced matchings in bipartite graphs
- On the approximability of the maximum induced matching problem
- 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 induced matching problem
- On the small cycle transversal of planar graphs
- Parameterized algorithms
- Parameterized computational complexity of Dodgson and Young elections
- Polynomial-time data reduction for dominating set
- Some results on graphs without long induced paths
- The parameterized complexity of the induced matching problem
- Which Codes Have$4$-Cycle-Free Tanner Graphs?
Cited in
(6)- Kernelization for cycle transversal problems
- Kernelization for cycle transversal problems
- On the small cycle transversal of planar graphs
- Planar vertex-disjoint cycle packing: new structures and improved kernel
- On the small cycle transversal of planar graphs
- Improved kernels for several problems on planar graphs
This page was built for publication: New kernels for several problems on planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285156)
