Complexity results for identifying codes in planar graphs
From MaRDI portal
Publication:3002553
DOI10.1111/j.1475-3995.2009.00750.xzbMath1219.05178OpenAlexW2073233463MaRDI QIDQ3002553
Olivier Hudry, Irène Charon, David Auger, Antoine C. Lobstein
Publication date: 20 May 2011
Published in: International Transactions in Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1111/j.1475-3995.2009.00750.x
Related Items (10)
More results on the complexity of identifying problems in graphs ⋮ Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ On the size of identifying codes in triangle-free graphs ⋮ Watching systems in graphs: an extension of identifying codes ⋮ Identifying codes of corona product graphs ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Locating-Domination and Identification ⋮ Identifying Codes in Trees and Planar Graphs ⋮ Bounding the trace function of a hypergraph with applications
Cites Work
- Identifying codes of cycles with odd orders
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Construction of codes identifying sets of vertices
- Identifying and locating-dominating codes on chains and cycles
- Approximability of identifying codes and locating-dominating codes
- Locating sensors in paths and cycles: the case of 2-identifying codes
- Identifying codes of cycles
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- On a new class of codes for identifying vertices in graphs
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity results for identifying codes in planar graphs
