Eleonora Guerrini
Extremal graphs for the identifying code problem.
Fri, 04/30/2010 - 15:01 — SomNambulAuthors: Eleonora Guerrini, Aline Parreau, Florent Foucaud, Matjaz Kovse, Reza Naserasr, Petru Valicov
Subjects: Discrete Mathematics
AbstractAn identifying code of a graph G is a dominating set C such that every vertex
x of G is distinguished from all other vertices by the set of vertices in C
that are at distance at most 1 from x. The problem of finding an identifying
code of minimum possible size turned out to be a challenging problem. It was
proved by N. Bertrand that if a graph on n vertices with at least one edge
admits an identifying code, then a minimum identifying code has size at most
n-1.Computing the distance distribution of systematic non-linear codes.
Thu, 09/10/2009 - 10:12 — SomNambulAuthors: Eleonora Guerrini, Emmanuela Orsini, Massimiliano Sala
Subjects: Discrete Mathematics
AbstractThe most important families of non-linear codes are systematic. A brute-force
check is the only known method to compute their weight distribution and
distance distribution. On the other hand, it outputs also all closest word
pairs in the code. In the black-box complexity model, the check is optimal
among closest-pair algorithms. In this paper we provide a Groebner basis
technique to compute the weight/distance distribution of any systematic
non-linear code. Also our technique outputs all closest pairs. Unlike the
check, our method can be extended to work on code families.
User login
