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

DOI10.1016/J.ENDM.2017.10.043MaRDI QIDQ2413180zbMATH OpenOpenAlexFDO

Authors Annegret K. Wagler, Gabriela R. Argiroffo, Silvia M. Bianchi, 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

block graphscomputational complexityidentifying codes

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Graph designs and isomorphic decomposition (05C51) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of error-correcting codes and error-detecting codes (94B99)

Recommendations

• Linear-time algorithms for three domination-based separation problems in block graphs
• Identifying codes in trees and planar graphs
• Identifying codes in line graphs
• The complexity of the identifying code problem in restricted graph classes
• Polyhedra associated with identifying codes in graphs

Cites work

• Distance-hereditary graphs
• Identifying and locating-dominating codes on chains and cycles
• 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.
• On a new class of codes for identifying vertices in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• On metric properties of certain clique graphs
• Study of identifying code polyhedra for some families of split graphs
• The complexity of the identifying code problem in restricted graph classes

Cited in

(4)

• 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
• Study of identifying code polyhedra for some families of split graphs
• Locating-domination and identification

This page was built for publication: A linear-time algorithm for the identifying code problem on block graphs

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