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 -