Name
Abstract | ||
|---|---|---|
Let K(n,r) denote the minimum cardinality of a binarycovering code of length n and covering radius r.Constructions of covering codes give upper bounds on K(n,r).It is here shown how computer searches for covering codes canbe sped up by requiring that the code has a given (not necessarilyfull) automorphism group. Tabu search is used to find orbitsof words that lead to a covering. In particular, a code Dis found which proves K(13,1) \leq 704, a new record.A direct construction of D is given, and its fullautomorphism group is shown to be the general linear group GL(3,3).It is proved that D is a perfect dominating set(each word not in D is covered by exactly one wordin D) and is a counterexample to the recent UniformityConjecture of Weichsel. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1023/A:1008326409439 | Des. Codes Cryptography |
Keywords | Field | DocType |
automorphism group,covering code,dominating set,hypercube,tabu search | Discrete mathematics,Dominating set,Combinatorics,Covering code,Automorphism,Cardinality,General linear group,Counterexample,Covering group,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 1 | 1573-7586 |
Citations | PageRank | References |
5 | 0.53 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patric R. J. Östergård | 1 | 5 | 0.53 |
| William D. Weakley | 2 | 56 | 10.40 |