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

MaRDI QIDQ5207845zbMATH OpenFDO

Authors A. Ahadi, A. Dehghan

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1605.01319, https://dmtcs.episciences.org/5678/pdf

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)

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

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)