Abstract | ||
---|---|---|
Given a subset X of vertices of the n-cube (i.e., the n-dimensional Hamming space), we are interested in the solution of the traveling salesman problem; namely, the minimal length of a cycle passing through all vertices of X. For a given number M, we estimate the maximum of these lengths when X ranges over all possible choices of sets of M vertices. Asymptotically, our estimates show that for a number M of vertices growing exponentially in n, the maximum is attained for a code with maximal possible minimum distance |
Year | DOI | Venue |
---|---|---|
1996 | 10.1109/18.508858 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
m vertex,salesman problem,binary hamming space,minimal length,maximal possible minimum distance,subset x,x range,possible choice,number m,n-dimensional hamming space,traveling salesman problem,gray codes,indexing terms,space exploration,hardware,minimisation,gray code,application software,hamming distance,vertices,data compression,linear code,testing | Graph center,Hamming code,Discrete mathematics,Combinatorics,Vertex (geometry),Gray code,Travelling salesman problem,Hamming distance,Linear code,Hamming space,Mathematics | Journal |
Volume | Issue | ISSN |
42 | 4 | 0018-9448 |
Citations | PageRank | References |
1 | 0.35 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gérard Cohen | 1 | 877 | 176.34 |
S. Litsyn | 2 | 602 | 50.31 |
G. Zemor | 3 | 232 | 16.71 |