Lossy Kernels for Connected Dominating Set on Sparse Graphs
From MaRDI portal
Publication:5234662
DOI10.1137/18M1172508zbMath1430.68195OpenAlexW2976369687WikidataQ127201832 ScholiaQ127201832MaRDI QIDQ5234662
Amer E. Mouawad, Sebastian Siebertz, Fahad Panolan, Eduard Eiben, Mithilesh Kumar
Publication date: 30 September 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1172508
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (7)
Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Lossy kernelization of same-size clustering ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ Constant round distributed domination on graph classes with bounded expansion
Cites Work
- Kernelization using structural parameters on sparse graph classes
- Fundamentals of parameterized complexity
- Sparsity. Graphs, structures, and algorithms
- A linear kernel for a planar connected dominating set
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Colouring graphs with bounded generalized colouring number
- Characterising bounded expansion by neighbourhood complexity
- Reconfiguration on sparse graphs
- Orderings on graphs and game coloring number
- Constant-factor approximation of the domination number in sparse graphs
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- On nowhere dense graphs
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Colouring and Covering Nowhere Dense Graphs
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- FPT Algorithms for Domination in Biclique-Free Graphs
- Domination Problems in Nowhere-Dense Classes
- Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
- FPT Algorithms for Connected Feedback Vertex Set
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Polynomial-time data reduction for dominating set
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Graph Classes: A Survey
- Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
- Kernelization and Sparseness: the case of Dominating Set
- The Generalised Colouring Numbers on Classes of Bounded Expansion
- Deciding First-Order Properties of Nowhere Dense Graphs
- Kernelization
- First order properties on nowhere dense structures
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Lossy kernelization
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- On the number of types in sparse graphs
- (Meta) Kernelization
- On the parameterized complexity of approximating dominating set
- Bidimensionality and Geometric Graphs
- Parameterized Algorithms
- On the generalised colouring numbers of graphs that exclude a fixed minor
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Lossy Kernels for Connected Dominating Set on Sparse Graphs
