More results on the complexity of domination problems in graphs

DOI10.1504/IJICOT.2017.10004701zbMath1407.68191OpenAlexW2607172406MaRDI QIDQ1664084

Olivier Hudry, Antoine C. Lobstein

Publication date: 24 August 2018

Published in: International Journal of Information and Coding Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1504/ijicot.2017.10004701

zbMATH Keywords

complexitycovering radiusgraph theoryNP-completenesspolynomial hierarchyhardnesscomplexity classesdominating codes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Some rainbow problems in graphs have complexity equivalent to satisfiability problems