A linear-time algorithm for the identifying code problem on block graphs

DOI10.1016/j.endm.2017.10.043zbMath1441.05151MaRDI QIDQ2413180

Gabriela R. Argiroffo, Silvia M. Bianchi, Annegret K. Wagler, Yanina P. Lucarini

Publication date: 9 April 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2017.10.043

zbMATH Keywords

computational complexity; block graphs; identifying codes

Mathematics Subject Classification ID

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