Some rainbow problems in graphs have complexity equivalent to satisfiability problems
From MaRDI portal
Cites work
- Block graphs with unique minimum dominating sets
- Complexity of unique (optimal) solutions in graphs: vertex cover and domination
- Connected tropical subgraphs in vertex-colored graphs
- scientific article; zbMATH DE number 5942290 (Why is no real title available?)
- scientific article; zbMATH DE number 4053685 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 841590 (Why is no real title available?)
- Identifying codes and locating-dominating sets on paths and cycles
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- More results on the complexity of domination problems in graphs
- On identifying codes
- On the complexity of unique solutions
- On the unique satisfiability problem
- Rainbow domination in graphs
- The complexity of facets (and some facets of complexity)
- The complexity of theorem-proving procedures
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
This page was built for publication: Some rainbow problems in graphs have complexity equivalent to satisfiability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071083)
