More results on the complexity of domination problems in graphs

DOI10.1504/IJICOT.2017.10004701zbMATH Open1407.68191OpenAlexW2607172406MaRDI QIDQ1664084FDOQ1664084

Antoine Lobstein, Olivier Hudry

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

Recommendations

• Some recent results on domination in graphs
• Some results on domination in graphs
• The algorithmic complexity of domination digraphs
• scientific article
• Complexity of Total {k}-Domination and Related Problems
• On the complexity of strong and weak total domination in graphs
• Algorithmic aspects of some variants of domination in graphs
• The complexity of domination problems in circle graphs
• Improved algorithms and complexity results for power domination in graphs
• Fundamentals of Computation Theory

zbMATH Keywords

graph theorycomplexitycomplexity classesNP-completenesshardnesspolynomial hierarchycovering radiusdominating 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)

Cited In (3)

• Title not available (Why is that?)
• Some rainbow problems in graphs have complexity equivalent to satisfiability problems
• Fundamentals of Computation Theory

This page was built for publication: More results on the complexity of domination problems in graphs

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