Domination chain: characterisation, classical complexity, parameterised complexity and approximability
DOI10.1016/j.dam.2019.10.005zbMath1439.05174MaRDI QIDQ2181241
Henning Fernau, Cristina Bazgan, Ljiljana Brankovic, Katrin Casel
Publication date: 18 May 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://basepub.dauphine.psl.eu/handle/123456789/22260
special graph classes; parameterised complexity; approximation complexity; domination chain; classical complexity
05C10: Planar graphs; geometric and topological aspects of graph theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q27: Parameterized complexity, tractability and kernelization