TY - JOUR
T1 - Weighted maximum matchings and optimal equi-difference conflict-avoiding codes
AU - Lo, Yuan Hsun
AU - Fu, Hung-Lin
AU - Lin, Yi Hean
PY - 2015/8/18
Y1 - 2015/8/18
N2 - A conflict-avoiding code (CAC)C of length n and weight k is a collection of k-subsets of Zn such that Δ(x)∩Δ(y)=∅ for any x,y∈C and x≠y, where Δ(x)={a-b:a,b∈x,a≠b}. Let CAC(n,k) denote the class of all CACs of length n and weight k. A CAC C∈CAC(n,k) is said to be equi-difference if any codeword x∈C has the form {0,i,2i,…,(k-1)i}. A CAC with maximum size is called optimal. In this paper we propose a graphical characterization of an equi-difference CAC, and then provide an infinite number of optimal equi-difference CACs for weight four.
AB - A conflict-avoiding code (CAC)C of length n and weight k is a collection of k-subsets of Zn such that Δ(x)∩Δ(y)=∅ for any x,y∈C and x≠y, where Δ(x)={a-b:a,b∈x,a≠b}. Let CAC(n,k) denote the class of all CACs of length n and weight k. A CAC C∈CAC(n,k) is said to be equi-difference if any codeword x∈C has the form {0,i,2i,…,(k-1)i}. A CAC with maximum size is called optimal. In this paper we propose a graphical characterization of an equi-difference CAC, and then provide an infinite number of optimal equi-difference CACs for weight four.
KW - Conflict-avoiding code
KW - Equi-difference conflict-avoiding code
KW - Weighted matching
UR - http://www.scopus.com/inward/record.url?scp=84931559963&partnerID=8YFLogxK
U2 - 10.1007/s10623-014-9961-5
DO - 10.1007/s10623-014-9961-5
M3 - Article
AN - SCOPUS:84931559963
VL - 76
SP - 361
EP - 372
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
SN - 0925-1022
IS - 2
ER -