Construction of codes identifying sets of vertices
type: Item
instance of: scholarly article
title: Construction of codes identifying sets of vertices
zbMATH Open document ID: 1060.05091
author: Sylvain Gravier
author: Julien Moncel
published in: The Electronic Journal of Combinatorics
publication date: 2005-04-25T00:00:00Z
full work available at URL: https://eudml.org/doc/124425
full work available at URL: v12i1r13.html
review text: Summary: The problem of constructing graphs having a \((1,\leq \ell)\)-identifying code of small cardinality is addressed. It is known that the cardinality of such a code is bounded by \(\Omega(\frac{\ell^2}{\log\ell}\log n)\). Here we construct graphs on \(n\) vertices having a \((1,\leq\! \ell)\)-identifying code of cardinality \(O(\ell^4 \log n)\) for all \(\ell\! \geq 2\). We derive our construction from a connection between identifying codes and superimposed codes, which we describe in this paper.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 94C12
zbMATH DE Number: 2161314
zbMATH Keywords: identifying codes
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2161314