Weighted maximum matchings and optimal equi-difference conflict-avoiding codes

Yuan Hsun Lo*, Hung-Lin Fu, Yi Hean Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)361-372
Number of pages12
JournalDesigns, Codes, and Cryptography
Volume76
Issue number2
DOIs
StatePublished - 18 Aug 2015

Keywords

  • Conflict-avoiding code
  • Equi-difference conflict-avoiding code
  • Weighted matching

Fingerprint Dive into the research topics of 'Weighted maximum matchings and optimal equi-difference conflict-avoiding codes'. Together they form a unique fingerprint.

Cite this