Edge identifying codes

MaRDI QIDQ2857369zbMATH OpenFDO

Authors Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau, Petru Valicov

Publication date 1 November 2013

Full work available at URL http://www.sciencedirect.com/science/article/pii/S1571065311001259

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• On identifying codes
• Connected Identifying Codes
• Identifying codes in line digraphs
• Codes Identifying Vertices in Graphs
• Identifying codes in line graphs
• An optimal edge-robust identifying code in the triangular lattice
• scientific article; zbMATH DE number 2081125
• On identifying codes that are robust against edge changes
• Bounds on identifying codes
• scientific article; zbMATH DE number 1262740

Cites work

• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Extremal graphs for the identifying code problem
• Line perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• 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 graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
• On the size of identifying codes in triangle-free graphs
• The Complexity of Multiterminal Cuts

Cited in

(2)

• Identifying codes in line graphs
• scientific article; zbMATH DE number 5022934 (Why is no real title available?)

This page was built for publication: Edge identifying codes

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