Discriminating codes in bipartite graphs

E. Charbit; I. Charon; G. Cohen; O. Hudry

doi:10.1016/j.endm.2006.08.005

Discriminating codes in bipartite graphs

E. Charbit
, I. Charon
, G. Cohen
, O. Hudry

Telecom Paris

Research output: Contribution to journal › Article › peer-review

Abstract

We study some combinatorial and algorithmic properties of discriminating codes in bipartite graphs. In particular, we provide bounds on minimum discriminating codes and give constructions. We also show that upperbounding the size of a discriminating code is NP-complete.

Original language	English
Pages (from-to)	29-35
Number of pages	7
Journal	Electronic Notes in Discrete Mathematics
Volume	26
DOIs	https://doi.org/10.1016/j.endm.2006.08.005
Publication status	Published - 1 Sept 2006

Keywords

Coverings
bipartite graphs
complexity
identifying codes

Access to Document

10.1016/j.endm.2006.08.005

Cite this

@article{07eca3fa2d244b079e0bf9c44a6b540c,

title = "Discriminating codes in bipartite graphs",

abstract = "We study some combinatorial and algorithmic properties of discriminating codes in bipartite graphs. In particular, we provide bounds on minimum discriminating codes and give constructions. We also show that upperbounding the size of a discriminating code is NP-complete.",

keywords = "Coverings, bipartite graphs, complexity, identifying codes",

author = "E. Charbit and I. Charon and G. Cohen and O. Hudry",

year = "2006",

month = sep,

day = "1",

doi = "10.1016/j.endm.2006.08.005",

language = "English",

volume = "26",

pages = "29--35",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

}

TY - JOUR

T1 - Discriminating codes in bipartite graphs

AU - Charbit, E.

AU - Charon, I.

AU - Cohen, G.

AU - Hudry, O.

PY - 2006/9/1

Y1 - 2006/9/1

N2 - We study some combinatorial and algorithmic properties of discriminating codes in bipartite graphs. In particular, we provide bounds on minimum discriminating codes and give constructions. We also show that upperbounding the size of a discriminating code is NP-complete.

AB - We study some combinatorial and algorithmic properties of discriminating codes in bipartite graphs. In particular, we provide bounds on minimum discriminating codes and give constructions. We also show that upperbounding the size of a discriminating code is NP-complete.

KW - Coverings

KW - bipartite graphs

KW - complexity

KW - identifying codes

UR - https://www.scopus.com/pages/publications/33747803341

U2 - 10.1016/j.endm.2006.08.005

DO - 10.1016/j.endm.2006.08.005

M3 - Article

AN - SCOPUS:33747803341

SN - 1571-0653

VL - 26

SP - 29

EP - 35

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Discriminating codes in bipartite graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this