Parameterized and approximation complexity of the detection pair problem in graphs

DOI10.7155/jgaa.00449zbMath1372.05220arXiv1601.05003OpenAlexW3104926434MaRDI QIDQ5371038

Florent Foucaud, Ralf Klasing

Publication date: 24 October 2017

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.05003

zbMATH Keywords

approximation algorithmdominating setparameterized complexitymetric dimensiondetection pair

Mathematics Subject Classification ID

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) Approximation algorithms (68W25)

This page was built for publication: Parameterized and approximation complexity of the detection pair problem in graphs