Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
type: Item
instance of: scholarly article
title: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
zbMATH Open document ID: 1044.68066
DOI: 10.1016/S0304-3975(02)00536-4
author: Irène Charon
author: Olivier Hudry
author: Antoine Lobstein
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1965256
zbMATH Keywords: Complexity
zbMATH Keywords: Coding theory
zbMATH Keywords: Graph
zbMATH Keywords: Identifying code
zbMATH Keywords: Locating-dominating code
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
cites work: Q4023377
cites work: On identifying codes
cites work: Q3789614
cites work: Q4368728
cites work: On a new class of codes for identifying vertices in graphs
full work available at URL: s0304-3975(02)00536-4
OpenAlex ID: W1967536892
description: scientific article; zbMATH DE number 1965256