New kernels for several problems on planar graphs
DOI10.1016/j.tcs.2019.09.024zbMath1436.68263OpenAlexW2975609250WikidataQ127198155 ScholiaQ127198155MaRDI QIDQ2285156
Jianxin Wang, Qilong Feng, Neng Huang, Beilin Zhuo, Guanlan Tan
Publication date: 16 January 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2019.09.024
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)
Cites Work
- Unnamed Item
- Unnamed Item
- On the small cycle transversal of planar graphs
- Improved induced matchings in sparse graphs
- On the induced matching problem
- Irredundancy in circular arc graphs
- Approximating maximum agreement forest on multiple binary trees
- Approximability results for the maximum and minimum maximal induced matching problems
- Equitable list colorings of planar graphs without short cycles
- The parameterized complexity of the induced matching problem
- Some results on graphs without long induced paths
- Matching theory
- NP-completeness of some generalizations of the maximum matching problem
- Induced matchings
- Maximum cuts and judicious partitions in graphs without short cycles
- On the chromatic number of triangle-free graphs of large minimum degree
- Induced matchings in intersection graphs.
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- 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
- On the approximability of the maximum induced matching problem
- Finding a maximum induced matching in weakly chordal graphs
- On maximum induced matchings in bipartite graphs
- On a conjecture of Tuza about packing and covering of triangles
- New results on induced matchings
- Parameterized computational complexity of Dodgson and Young elections
- Improved PTAS for the constrained \(k\)-means problem
- On the chromatic number of pentagon-free graphs of large minimum degree
- Edge-disjoint packing of stars and cycles
- On Generating Triangle-Free Graphs
- Which Codes Have$4$-Cycle-Free Tanner Graphs?
- Kernelization for Cycle Transversal Problems
- Polynomial-time data reduction for dominating set
- Kernelization
- Node-and edge-deletion NP-complete problems
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Algorithms – ESA 2004
- Parameterized Algorithms
- Approximation and Online Algorithms
- Approximating Maximum Subgraphs without Short Cycles
This page was built for publication: New kernels for several problems on planar graphs
