Linear Problem Kernels for NP-Hard Problems on Planar Graphs
From MaRDI portal
Recommendations
- Linear problem kernels for planar graph problems with small distance property
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- scientific article; zbMATH DE number 2089218
- Planar graph vertex partition for linear problem kernels
- A linear kernel for a planar connected dominating set
Cited in
(45)- The parameterized complexity of the induced matching problem
- On problems without polynomial kernels
- Explicit linear kernels for packing problems
- Towards optimal kernel for connected vertex cover in planar graphs
- New kernels for several problems on planar graphs
- Capacitated domination: problem complexity and approximation algorithms
- Towards optimal kernel for edge-disjoint triangle packing
- Edge-disjoint packing of stars and cycles
- A systematic study on meta-heuristic approaches for solving the graph coloring problem
- An improved kernel for planar vertex-disjoint triangle packing
- Simpler linear-time kernelization for planar dominating set
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- An improved kernel for planar connected dominating set
- scientific article; zbMATH DE number 2089218 (Why is no real title available?)
- On the small cycle transversal of planar graphs
- A 13k-kernel for planar feedback vertex set via region decomposition
- Linear problem kernels for planar graph problems with small distance property
- Kernelization of edge perfect code and its variants
- Kernelization using structural parameters on sparse graph classes
- Edge-disjoint packing of stars and cycles
- Capacitated Domination and Covering: A Parameterized Perspective
- Planar graph vertex partition for linear problem kernels
- Polynomial kernels for hard problems on disk graphs
- A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
- The Planar k-Means Problem is NP-Hard
- Kernelization: new upper and lower bound techniques
- Planar capacitated dominating set is \(W[1]\)-hard
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Improved linear problem kernel for planar connected dominating set
- Kernelization for cycle transversal problems
- Confronting intractability via parameters
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- Linear Vertex-kernels for Several Dense Ranking r -Constraint Satisfaction Problems
- Coverability and sub-exponential parameterized algorithms in planar graphs
- A Retrospective on (Meta) Kernelization
- A linear kernel for planar red-blue dominating set
- A \(9k\) kernel for nonseparating independent set in planar graphs
- A linear kernel for a planar connected dominating set
- scientific article; zbMATH DE number 6784970 (Why is no real title available?)
- Perfect domination and small cycles
- On the small cycle transversal of planar graphs
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Fixed-parameter linear-time algorithms for NP-hard graph and hypergraph problems arising in industrial applications
This page was built for publication: Linear Problem Kernels for NP-Hard Problems on Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428824)
