Complexity results for identifying codes in planar graphs
From MaRDI portal
Recommendations
- Identifying codes in trees and planar graphs
- The complexity of the identifying code problem in restricted graph classes
- scientific article; zbMATH DE number 4070305
- On a code problem concerning planar acyclic graphs
- Minimal identifying codes in trees and planar graphs with large girth
- Discriminating codes in (bipartite) planar graphs
- On a new class of identifying codes in graphs
- Extremal graphs for the identifying code problem
- On a new class of codes for identifying vertices in graphs
- New bounds for codes identifying vertices in graphs
Cites work
- Approximability of identifying codes and locating-dominating codes
- Construction of codes identifying sets of vertices
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
- Identifying and locating-dominating codes on chains and cycles
- Identifying codes of cycles
- Identifying codes of cycles with odd orders
- Locating sensors in paths and cycles: the case of 2-identifying codes
- 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 admitting codes identifying sets of vertices
- The Rectilinear Steiner Tree Problem is NP-Complete
Cited in
(18)- More results on the complexity of identifying problems in graphs
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- Identifying and locating-dominating codes in (random) geometric networks
- Identifying codes in hereditary classes of graphs and VC-dimension
- Minimal identifying codes in trees and planar graphs with large girth
- Planar Convex Codes are Decidable
- On the size of identifying codes in triangle-free graphs
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- The complexity of the identifying code problem in restricted graph classes
- Locating-domination and identification
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- On Iiro Honkala's contributions to identifying codes
- Watching systems in graphs: an extension of identifying codes
- Identifying codes in trees and planar graphs
- Identifying codes of corona product graphs
- Discriminating codes in (bipartite) planar graphs
- Bounding the trace function of a hypergraph with applications
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
This page was built for publication: Complexity results for identifying codes in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002553)
