The complexity of the identifying code problem in restricted graph classes

DOI10.1007/978-3-642-45278-9_14MaRDI QIDQ2870024zbMATH OpenOpenAlexFDO

Authors Florent Foucaud

Publication date 17 January 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45278-9_14

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Complexity results for identifying codes in planar graphs
• Identifying codes in trees and planar graphs
• Minimal identifying codes in trees and planar graphs with large girth
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.

Cited in

(20)

• Progress on the description of identifying code polyhedra for some families of split graphs
• Polyhedra associated with identifying codes in graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs
• The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations
• On the complexity of the identifiable subgraph problem
• On the complexity of the identifiable subgraph problem, revisited
• Approximability of identifying codes and locating-dominating codes
• A linear-time algorithm for the identifying code problem on block graphs
• Watching systems in graphs: an extension of identifying codes
• More results on the complexity of identifying problems in graphs
• Identifying codes in trees and planar graphs
• Complexity results for identifying codes in planar graphs
• Study of identifying code polyhedra for some families of split graphs
• Discriminating codes in bipartite graphs
• Identifying codes in hereditary classes of graphs and VC-dimension
• The identifying code number and Mycielski's construction of graphs
• Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm
• Some results about a conjecture on identifying codes in complete suns
• On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs

This page was built for publication: The complexity of the identifying code problem in restricted graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870024)