A \(9k\) kernel for nonseparating independent set in planar graphs
From MaRDI portal
Publication:385964
DOI10.1016/j.tcs.2013.11.021zbMath1277.68096arXiv1207.4666MaRDI QIDQ385964
Publication date: 13 December 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.4666
planar graphs; kernelization; connected vertex cover; fixed parameter algorithms; nonseparating independent set
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
05C10: Planar graphs; geometric and topological aspects of graph theory
Related Items
Extension and its price for the connected vertex cover problem, Known Algorithms for Edge Clique Cover are Probably Optimal
Cites Work
- FPT algorithms for connected feedback vertex set
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Maximum genus and maximum nonseparating independent set of a 3-regular graph
- Towards optimal kernel for connected vertex cover in planar graphs
- Kernelization – Preprocessing with a Guarantee
- Linear Problem Kernels for Planar Graph Problems with Small Distance Property
- Kernel(s) for problems with no kernel
- Spanning Trees with Many Leaves
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Bidimensionality and Geometric Graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
