More results on the complexity of identifying problems in graphs
From MaRDI portal
Publication:264560
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
graph theoryNP-completenesspolynomial hierarchyhardnessidentifying codescomplexity classestwin-free graphs
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