Minimal identifying codes in trees and planar graphs with large girth

DOI10.1016/j.ejc.2009.11.012zbMath1221.05035OpenAlexW1965065197MaRDI QIDQ976158

David Auger

Publication date: 17 June 2010

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2009.11.012

zbMATH Keywords

finite undirected graph

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (23)

More results on the complexity of identifying problems in graphs ⋮ Identifying codes in the complementary prism of cycles ⋮ Revisiting and Improving Upper Bounds for Identifying Codes ⋮ Identifying Codes in Line Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ A linear-time algorithm for the identifying code problem on block graphs ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ Unnamed Item ⋮ On the size of identifying codes in triangle-free graphs ⋮ Identifying codes and watching systems in Kneser graphs ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Progress on the description of identifying code polyhedra for some families of split graphs ⋮ Polyhedra associated with identifying codes in graphs ⋮ The identifying code number and Mycielski's construction of graphs ⋮ Unnamed Item ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Locating-Domination and Identification ⋮ Improved lower bound for locating-dominating codes in binary Hamming spaces ⋮ Unnamed Item ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs ⋮ Identifying Codes in Trees and Planar Graphs

Cites Work

• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On cages admitting identifying codes
• A linear algorithm for minimum 1-identifying codes in oriented trees
• Domination and location in acyclic graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On a new class of codes for identifying vertices in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimal identifying codes in trees and planar graphs with large girth