0000000000759215
AUTHOR
Jarmo Ernvall
Estimating the length of minimal spanning trees in compression of files
Compression of a formatted file by a minimal spanning tree (MST) is studied. Here the records of the file are considered as the nodes of a weighted undirected graph. Each record pair is connected in the graph and the corresponding arc is weighted by the sum of field lengths of those fields which differ in the two records. The actual compression is made by constructing an MST of the graph and by storing it in an economic way to preserve the information of the file. The length of the MST is a useful measure in the estimation of the power of the compression. In the paper we study upper bounds of this length, especially in the case where the field lengths of the different fields may vary. The u…
NP-completeness of the hamming salesman problem
It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.