0000000000759215

AUTHOR

Jarmo Ernvall

showing 2 related works from this author

Estimating the length of minimal spanning trees in compression of files

1984

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…

Discrete mathematicsSpanning treeComputer Networks and CommunicationsApplied MathematicsShortest-path treeMinimum spanning treeConnected dominating setCombinatoricsComputational MathematicsGraph (abstract data type)Undirected graphSoftwareMathematicsofComputing_DISCRETEMATHEMATICSMathematicsMinimum degree spanning treeBIT
researchProduct

NP-completeness of the hamming salesman problem

1985

It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.

Discrete mathematicsComputer Networks and CommunicationsApplied MathematicsComputer Science::Neural and Evolutionary ComputationHamming distanceComputer Science::Computational ComplexityTravelling salesman problemCombinatoricsHigh Energy Physics::TheoryComputational MathematicsCompleteness (order theory)Computer Science::Data Structures and AlgorithmsNP-completeBottleneck traveling salesman problemHamming codeSoftwareComputer Science::Information TheoryMathematicsBIT
researchProduct