DISCRIMINATING CODES IN BIPARTITE GRAPHS: BOUNDS, EXTREMAL CARDINALITIES, COMPLEXITY

被引：20

作者：

Charbit, Emmanuel ^{[1
]}

Charon, Irene ^{[1
,2
]}

Cohen, Gerard ^{[1
,2
]}

Hudry, Olivier ^{[1
,2
]}

Lobstein, Antoine ^{[1
,2
]}

机构：

[1] TELECOM ParisTech, Inst TELECOM, F-75634 Paris 13, France

[2] CNRS, LTCI, UMR 5141, F-75634 Paris 13, France

来源：

ADVANCES IN MATHEMATICS OF COMMUNICATIONS | 2008年 / 2卷 / 04期

关键词：

Graph theory; bipartite graphs; discriminating codes; identifying codes; locating-dominating codes; separating codes; complexity;

D O I：

10.3934/amc.2008.2.403

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Consider an undirected bipartite graph G = (V = I boolean OR A, E), with no edge inside I nor A. For any vertex v is an element of V, let N(v) be the set of neighbours of v. A code C subset of A is said to be discriminating if all the sets N(i) boolean AND C, i is an element of I, are nonempty and distinct. We study some properties of discriminating codes. In particular, we give bounds on the minimum size of these codes, investigate graphs where minimal discriminating codes have size close to the upper bound, or give the exact minimum size in particular graphs; we also give an NP-completeness result.

引用

页码：403 / 420

页数：18

共 36 条

[31] Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs
Naparstek, Oshri
Leshem, Amir
RANDOM STRUCTURES & ALGORITHMS, 2016, 48 (02) : 384 - 395
[32] Optimal Bipartite Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterizations and Applications to Expander/LDPC Codes
Hoholdt, Tom
Janwal, Heeralal
APPLIED ALGEBRA, ALGEBRAIC ALGORITHMS, AND ERROR-CORRECTING CODES, 2009, 5527 : 53 - +
[33] A trellis-based method for removing cycles from bipartite graphs and construction of low density parity check codes
Lan, L
Tai, YY
Chen, L
Lin, S
Abdel-Ghaffar, K
IEEE COMMUNICATIONS LETTERS, 2004, 8 (07) : 443 - 445
[34] Binary codes and partial permutation decoding sets from biadjacency matrices of bipartite graphs Γ(2k, k, k+1, 1)
Fish, W.
Mumba, N. B.
Mwambene, E.
Rodrigues, B. G.
QUAESTIONES MATHEMATICAE, 2020, 43 (04) : 523 - 538
[35] Binary Codes and Partial Permutation Decoding Sets from Biadjacency Matrices of the Bipartite Graphs Γ (2k+1, k, k+2, 1)
Fish, W.
Mumba, N. B.
Mwambene, E.
Rodrigues, B. G.
GRAPHS AND COMBINATORICS, 2017, 33 (02) : 357 - 368
[36] Binary Codes and Partial Permutation Decoding Sets from Biadjacency Matrices of the Bipartite Graphs Γ(2k+1,k,k+2,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma (2k+1,k,k+2,1)$$\end{document}
W. Fish
N. B. Mumba
E. Mwambene
B. G. Rodrigues
Graphs and Combinatorics, 2017, 33 (2) : 357 - 368

← 1 2 3 4 →