On the minimum size of an identifying code over all orientations of a graph
From MaRDI portal
Publication:1753015
zbMath1392.05105MaRDI QIDQ1753015
Publication date: 25 May 2018
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p49
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (4)
On finding the best and worst orientations for the metric dimension ⋮ Extremal Digraphs for open neighbourhood location-domination and identifying codes ⋮ Locating-Domination and Identification ⋮ Locating-dominating sets: from graphs to oriented graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Identifying codes for infinite triangular grids with a finite number of rows
- A simplified NP-complete satisfiability problem
- On graphs having a \(V\setminus \{x\}\) set as an identifying code
- Some simplified NP-complete graph problems
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
- Extremal graphs for the identifying code problem
- New bounds on the minimum density of an identifying code for the infinite hexagonal grid
- A linear algorithm for minimum 1-identifying codes in oriented trees
- Minimum-Density Identifying Codes in Square Grids
- On a new class of codes for identifying vertices in graphs
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
- Reducibility among Combinatorial Problems
- Identifying Codes in Line Graphs
- Minimum density of identifying codes of king grids
This page was built for publication: On the minimum size of an identifying code over all orientations of a graph
