Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
type: Item
instance of: scholarly article
title: Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
zbMATH Open document ID: 1417.68069
author: Olivier Hudry
author: Antoine Lobstein
published in: Theoretical Computer Science
publication date: 2019-03-26T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 94B60
zbMATH DE Number: 7041824
zbMATH Keywords: complexity theory
zbMATH Keywords: graph theory
zbMATH Keywords: uniqueness of solution
zbMATH Keywords: polynomial reduction
zbMATH Keywords: locating-dominating codes
zbMATH Keywords: identifying codes
MaRDI profile type: Publication
full work available at URL: j.tcs.2018.09.034
OpenAlex ID: W2895699666
cites work: On the unique satisfiability problem
cites work: Q3089301
cites work: The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
cites work: Block graphs with unique minimum dominating sets
cites work: Q4863436
cites work: On the complexity of unique solutions
cites work: Q5615282
cites work: Q5315023
cites work: On a new class of codes for identifying vertices in graphs
cites work: Q3789614
cites work: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
cites work: On identifying codes
cites work: More results on the complexity of identifying problems in graphs
cites work: On the number of optimal identifying codes in a twin-free graph
cites work: On the ensemble of optimal dominating and locating-dominating codes in a graph
cites work: On the ensemble of optimal identifying codes in a twin-free graph
cites work: Identifying codes in trees and planar graphs
cites work: Minimal identifying codes in trees and planar graphs with large girth
cites work: Complexity results for identifying codes in planar graphs
cites work: Identifying Codes in Line Graphs
cites work: Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
cites work: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
cites work: Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
cites work: Approximability of identifying codes and locating-dominating codes
cites work: The complexity of facets (and some facets of complexity)
cites work: Q4198056
cites work: Q4385525
cites work: Q4298260
cites work: The complexity of theorem-proving procedures
cites work: Q4239067
Wikidata QID: Q129138991
DOI: 10.1016/J.TCS.2018.09.034
description: scientific article; zbMATH DE number 7041824