Polynomial kernels and wideness properties of nowhere dense graph classes

DOI10.1137/1.9781611974782.100MaRDI QIDQ4575843zbMATH OpenOpenAlexFDO

Authors Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

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

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

Recommendations

• Polynomial kernels and wideness properties of nowhere dense graph classes
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Domination problems in nowhere-dense classes of graphs
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs

Cited in

(18)

• Reconfiguration on nowhere dense graph classes
• Twin-width and polynomial kernels
• Constant round distributed domination on graph classes with bounded expansion
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Domination problems in nowhere-dense classes of graphs
• Lossy kernels for connected dominating set on sparse graphs
• Coloring and covering nowhere dense graphs
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Progressive algorithms for domination and independence
• Algorithmic properties of sparse digraphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
• Lossy kernels for connected dominating set on sparse graphs
• Directed nowhere dense classes of graphs
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• On finding short reconfiguration sequences between independent sets
• On the parameterized complexity of reconfiguration of connected dominating sets

This page was built for publication: Polynomial kernels and wideness properties of nowhere dense graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575843)