Some rainbow problems in graphs have complexity equivalent to satisfiability problems

DOI10.1111/itor.12847OpenAlexW3040750047MaRDI QIDQ6071083

Olivier Hudry, Antoine C. Lobstein

Publication date: 27 November 2023

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/itor.12847

zbMATH Keywords

graph theoryidentifying codescomplexity theoryuniqueness of solutiontwin-free graphslocating-dominating codesdominating codesrainbow sets

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identifying codes and locating-dominating sets on paths and cycles
• Rainbow domination in graphs
• The complexity of facets (and some facets of complexity)
• 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
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Tropical dominating sets in vertex-coloured graphs
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• On the unique satisfiability problem
• On the complexity of unique solutions
• The complexity of theorem-proving procedures
• Block graphs with unique minimum dominating sets

This page was built for publication: Some rainbow problems in graphs have complexity equivalent to satisfiability problems