More results on the complexity of identifying problems in graphs

DOI10.1016/j.tcs.2016.01.021zbMath1336.68130OpenAlexW2276120567MaRDI QIDQ264560

Olivier Hudry, Antoine C. Lobstein

Publication date: 31 March 2016

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

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

zbMATH Keywords

graph theoryNP-completenesspolynomial hierarchyhardnessidentifying codescomplexity classestwin-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

More results on the complexity of identifying problems in graphs, Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, On a conjecture regarding identification in Hamming graphs, On \(t\)-revealing codes in binary Hamming spaces, Tolerant location detection in sensor networks, Locating-Domination and Identification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• More results on the complexity of identifying problems in graphs
• On identifying codes in binary Hamming spaces
• The complexity of Kemeny elections
• New identifying codes in the binary Hamming space
• Minimal identifying codes in trees and planar graphs with large girth
• On the complexity of Slater's problems
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On the complexity of the identification problem in Hamming spaces
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
• Identifying Codes in Trees and Planar Graphs
• Complexity results for identifying codes in planar graphs
• On a new class of codes for identifying vertices in graphs
• Identifying Codes in Line Graphs