Unique (optimal) solutions: complexity results for identifying and locating-dominating codes

DOI10.1016/j.tcs.2018.09.034zbMath1417.68069OpenAlexW2895699666WikidataQ129138991 ScholiaQ129138991MaRDI QIDQ1733054

Olivier Hudry, Antoine C. Lobstein

Publication date: 26 March 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.09.034

zbMATH Keywords

graph theoryidentifying codescomplexity theoryuniqueness of solutionpolynomial reductionlocating-dominating codes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other types of codes (94B60) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Some rainbow problems in graphs have complexity equivalent to satisfiability problems ⋮ Locating-Domination and Identification ⋮ Improved lower bound for locating-dominating codes in binary Hamming spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• More results on the complexity of identifying problems in graphs
• On the ensemble of optimal identifying codes in a twin-free graph
• On the number of optimal identifying codes in a twin-free graph
• Minimal identifying codes in trees and planar graphs with large girth
• 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.
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• On the ensemble of optimal dominating and locating-dominating codes in a graph
• Approximability of identifying codes and locating-dominating codes
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Identifying Codes in Trees and Planar Graphs
• Complexity results for identifying codes in planar graphs
• On the unique satisfiability problem
• On the complexity of unique solutions
• On a new class of codes for identifying vertices in graphs
• Identifying Codes in Line Graphs
• The complexity of theorem-proving procedures
• Block graphs with unique minimum dominating sets

This page was built for publication: Unique (optimal) solutions: complexity results for identifying and locating-dominating codes