Complete complexity dichotomies for the dominating set problem

DOI10.1134/S0001434625010067MaRDI QIDQ6974179zbMATH OpenFDO

Authors D. S. Malyshev

Publication date 10 June 2025

Published in Mathematical Notes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0001434625010067

zbMATH Keywords

computational complexitydominating sethereditary class

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A complexity dichotomy and a new boundary class for the dominating set problem
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Boundary classes of graphs for the dominating set problem
• Classes of graphs critical for the edge list-ranking problem
• Continuous sets of the boundary classes of graphs for coloring problems
• Critical hereditary graph classes: a survey
• Dominating cliques in \(P_ 5\)-free graphs
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 7742925 (Why is no real title available?)
• NP-hard graph problems and boundary classes of graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Split Graphs Having Dilworth Number Two

This page was built for publication: Complete complexity dichotomies for the dominating set problem

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