Towards optimal kernel for connected vertex cover in planar graphs
From MaRDI portal
Publication:1949125
DOI10.1016/j.dam.2012.12.001zbMath1263.05021arXiv1110.1964OpenAlexW2097922076WikidataQ62046038 ScholiaQ62046038MaRDI QIDQ1949125
Łukasz Kowalik, Marcin Pilipczuk, Karol Suchan
Publication date: 25 April 2013
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.1964
Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)
Related Items (6)
A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Planar graph vertex partition for linear problem kernels ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ A 42k Kernel for the Complementary Maximal Strip Recovery Problem ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Planar graph vertex partition for linear problem kernels
- Improved induced matchings in sparse graphs
- The parameterized complexity of the induced matching problem
- Lower bounds on the cardinality of the maximum matchings of planar graphs
- Vertex Cover: Further Observations and Further Improvements
- A Linear Kernel for Planar Feedback Vertex Set
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Incompressibility through Colors and IDs
- Efficient Planarity Testing
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Bidimensionality and Geometric Graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
This page was built for publication: Towards optimal kernel for connected vertex cover in planar graphs
