Linear Problem Kernels for NP-Hard Problems on Planar Graphs
From MaRDI portal
Publication:5428824
DOI10.1007/978-3-540-73420-8_34zbMath1171.68488OpenAlexW1818723348MaRDI QIDQ5428824
Publication date: 28 November 2007
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73420-8_34
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (36)
Simpler Linear-Time Kernelization for Planar Dominating Set ⋮ Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ A Retrospective on (Meta) Kernelization ⋮ Edge-disjoint packing of stars and cycles ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Kernelization of edge perfect code and its variants ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Planar graph vertex partition for linear problem kernels ⋮ Unnamed Item ⋮ A systematic study on meta-heuristic approaches for solving the graph coloring problem ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Improved linear problem kernel for planar connected dominating set ⋮ An improved kernel for planar vertex-disjoint triangle packing ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Kernelization for cycle transversal problems ⋮ Towards optimal kernel for connected vertex cover in planar graphs ⋮ Perfect domination and small cycles ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Confronting intractability via parameters ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Explicit linear kernels for packing problems ⋮ An Improved Kernel for Planar Connected Dominating Set ⋮ A linear kernel for planar red-blue dominating set ⋮ A linear kernel for a planar connected dominating set ⋮ On the small cycle transversal of planar graphs ⋮ On the Small Cycle Transversal of Planar Graphs ⋮ New kernels for several problems on planar graphs ⋮ The parameterized complexity of the induced matching problem ⋮ On problems without polynomial kernels ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Planar Capacitated Dominating Set Is W[1-Hard] ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Capacitated domination: problem complexity and approximation algorithms
This page was built for publication: Linear Problem Kernels for NP-Hard Problems on Planar Graphs
