Polynomial kernels and wideness properties of nowhere dense graph classes. (English) Zbl 1454.05064

Kreutzer, Stephan; Rabinovich, Roman; Siebertz, Sebastian

ACM Trans. Algorithms 15, No. 2, Article No. 24, 19 p. (2019).

MSC:

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

Keywords:

graph structure theory; nowhere denseness; stability theory; uniform quasi-wideness

Citations:

Zbl 1206.03033; Zbl 1226.05102