(2/2/3)-SAT problem and its applications in dominating set problems

zbMATH Open1430.05031arXiv1605.01319MaRDI QIDQ5207845FDOQ5207845

Authors: A. Ahadi, A. Dehghan 

Publication date: 13 January 2020

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

Recommendations

• Satgraphs and independent domination. I
• Computational complexity of some restricted instances of 3-SAT
• A simplified NP-complete satisfiability problem
• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
• Polar SAT and related graphs

zbMATH Keywords

computational complexityregular graphsincidence coloringperfect codesindependent dominating set(2/2/3)-SAT

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cited In (1)

• End vertices of graph searches on bipartite graphs

This page was built for publication: (2/2/3)-SAT problem and its applications in dominating set problems

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