A linear kernel for a planar connected dominating set
From MaRDI portal
Publication:534569
DOI10.1016/J.TCS.2010.10.045zbMATH Open1216.68131OpenAlexW2177196747MaRDI QIDQ534569FDOQ534569
Matthias Mnich, Daniel Lokshtanov, Saket Saurabh
Publication date: 18 May 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.045
Recommendations
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)
Cites Work
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- `` Strong NP-Completeness Results
- 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
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Approximation algorithms for connected dominating sets
- Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
- Solving connected dominating set faster than \(2^n\)
- Vertex cover: Further observations and further improvements
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- Title not available (Why is that?)
- A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
Cited In (12)
- SOFSEM 2006: Theory and Practice of Computer Science
- Title not available (Why is that?)
- Improved linear problem kernel for planar connected dominating set
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- Smaller Kernels for Several FPT Problems Based on Simple Observations
- Kernelization and Sparseness: the case of Dominating Set
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Finding minimum weight connected dominating set in stochastic graph based on learning automata
- Improved kernel results for some FPT problems based on simple observations
- A linear kernel for planar red-blue dominating set
This page was built for publication: A linear kernel for a planar connected dominating set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534569)
