A linear-time algorithm for the identifying code problem on block graphs
From MaRDI portal
Publication:2413180
DOI10.1016/j.endm.2017.10.043zbMath1441.05151MaRDI QIDQ2413180
Annegret K. Wagler, Yanina P. Lucarini, Silvia M. Bianchi, Gabriela R. Argiroffo
Publication date: 9 April 2018
Full work available at URL: https://doi.org/10.1016/j.endm.2017.10.043
05B05: Combinatorial aspects of block designs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
94B99: Theory of error-correcting codes and error-detecting codes
05C51: Graph designs and isomorphic decomposition
Related Items
Progress on the description of identifying code polyhedra for some families of split graphs, Linear-time algorithms for three domination-based separation problems in block graphs
Cites Work
- On graphs having a \(V\setminus \{x\}\) set as an identifying code
- Minimal identifying codes in trees and planar graphs with large girth
- Distance-hereditary graphs
- On metric properties of certain clique graphs
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Identifying and locating-dominating codes on chains and cycles
- The Complexity of the Identifying Code Problem in Restricted Graph Classes
- Study of Identifying Code Polyhedra for Some Families of Split Graphs
- On a new class of codes for identifying vertices in graphs