On the minimum size of an identifying code over all orientations of a graph
type: Item
instance of: scholarly article
title: On the minimum size of an identifying code over all orientations of a graph
zbMATH Open document ID: 1392.05105
author: Nathann Cohen
author: Frédéric Havet
published in: The Electronic Journal of Combinatorics
publication date: 2018-05-25T00:00:00Z
full work available at URL: v25i1p49
review text: Summary: If \(G\) be a graph or a digraph, let \(\mathrm{id}(G)\) be the minimum size of an identifying code of \(G\) if one exists, and \(\mathrm{id}(G)=+\infty\) otherwise. For a graph \(G\), let \(\mathrm{idor}(G)\) be the minimum of \(\mathrm{id}(D)\) overall orientations \(D\) of \(G\). We give some lower and upper bounds on \(\mathrm{idor}(G)\). In particular, we show that \(\mathrm{idor}(G)\leqslant \frac{3}{2} \mathrm{id}(G)\) for every graph \(G\). We also show that computing \(\mathrm{idor}(G)\) is NP-hard, while deciding whether \(\mathrm{idor}(G)\leqslant |V(G)|-k\) is polynomial-time solvable for every fixed integer \(k\).
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6873093
zbMATH Keywords: identifying codes
zbMATH Keywords: orientation
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
cites work: Q5442540
cites work: Minimum-Density Identifying Codes in Square Grids
cites work: A linear algorithm for minimum 1-identifying codes in oriented trees
cites work: Identifying and locating-dominating codes: NP-completeness results for directed graphs
cites work: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
cites work: A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
cites work: New bounds on the minimum density of an identifying code for the infinite hexagonal grid
cites work: Identifying codes for infinite triangular grids with a finite number of rows
cites work: Minimum density of identifying codes of king grids
cites work: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
cites work: Identifying Codes in Line Graphs
cites work: Extremal graphs for the identifying code problem
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: On graphs having a \(V\setminus \{x\}\) set as an identifying code
cites work: Reducibility among Combinatorial Problems
cites work: On a new class of codes for identifying vertices in graphs
cites work: A simplified NP-complete satisfiability problem
description: scientific article; zbMATH DE number 6873093