Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes

DOI10.1137/1.9781611974782.100zbMath1410.05112OpenAlexW2514937286MaRDI QIDQ4575843

Roman Rabinovich, Sebastian Siebertz, Stephan Kreutzer

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.100

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

On the parameterized complexity of reconfiguration of connected dominating sets, Coloring and Covering Nowhere Dense Graphs, Reconfiguration on nowhere dense graph classes, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, Unnamed Item, Reconfiguration on sparse graphs, Unnamed Item, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness, Constant round distributed domination on graph classes with bounded expansion