Minimal identifying codes in trees and planar graphs with large girth
From MaRDI portal
Publication:976158
DOI10.1016/J.EJC.2009.11.012zbMATH Open1221.05035OpenAlexW1965065197MaRDI QIDQ976158FDOQ976158
Authors: 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
Recommendations
Cites Work
- Graph theory
- Title not available (Why is that?)
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- On a new class of codes for identifying vertices in graphs
- Locating-domination and identifying codes in trees
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Title not available (Why is that?)
- Domination and location in acyclic graphs
- On cages admitting identifying codes
- A linear algorithm for minimum 1-identifying codes in oriented trees
- Title not available (Why is that?)
Cited In (33)
- More results on the complexity of identifying problems in graphs
- The identifying code number and Mycielski's construction of graphs
- Choice identification of a graph
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- Identifying codes in hereditary classes of graphs and VC-dimension
- Revisiting and improving upper bounds for identifying codes
- Title not available (Why is that?)
- On the size of identifying codes in triangle-free graphs
- On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
- Identifying codes in the complementary prism of cycles
- Polyhedra associated with identifying codes in graphs
- Progress on the description of identifying code polyhedra for some families of split graphs
- The complexity of the identifying code problem in restricted graph classes
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Watching systems of triangular graphs
- Locating-domination and identification
- Identifying codes in line graphs
- Identifying codes with small radius in some infinite regular graphs
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- A linear-time algorithm for the identifying code problem on block graphs
- Identifying codes and watching systems in Kneser graphs
- Linear-time algorithms for three domination-based separation problems in block graphs
- On the minimum size of an identifying code over all orientations of a graph
- Identifying codes in trees and planar graphs
- Complexity results for identifying codes in planar graphs
- A linear algorithm for minimum 1-identifying codes in oriented trees
- Improved lower bound for locating-dominating codes in binary Hamming spaces
- On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
- Counting and coding identity trees with fixed diameter and bounded degree
- Edge identifying codes
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Identifying \(X\)-trees with few characters
This page was built for publication: Minimal identifying codes in trees and planar graphs with large girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976158)
