New kernels for several problems on planar graphs
From MaRDI portal
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) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- 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 agreement forest on multiple binary trees
- Approximating Maximum Subgraphs without Short Cycles
- 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
- scientific article; zbMATH DE number 434499 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- Improved induced matchings in sparse graphs
- Improved PTAS for the constrained \(k\)-means problem
- 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
- New results on induced matchings
- Node-and edge-deletion NP-complete problems
- NP-completeness of some generalizations of the maximum matching problem
- 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)- Planar vertex-disjoint cycle packing: new structures and improved kernel
- On the small cycle transversal of planar graphs
- Kernelization for cycle transversal problems
- Kernelization for cycle transversal problems
- 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)
