Identifying Codes in Trees and Planar Graphs

DOI10.1016/j.endm.2009.07.097zbMath1273.05045OpenAlexW1967057336MaRDI QIDQ2851521

David Auger

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph theoryplanar graphsNP-completenessidentifying codes

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (3)

More results on the complexity of identifying problems in graphs ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Minimum identifying codes in some graphs differing by matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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.
• Construction of codes identifying sets of vertices
• Complexity results for identifying codes in planar graphs
• On a new class of codes for identifying vertices in graphs

This page was built for publication: Identifying Codes in Trees and Planar Graphs