Cited By
View all- Ernvall JNevalainen O(1984)Estimating the length of minimal spanning trees in compression of filesBIT10.1007/BF0193451224:1(19-32)Online publication date: 1-Mar-1984
Compact storage schemes for formatted files by spanning trees
Authors: 
J. Ernvall, O. NevalainenAuthors Info & Claims
Abstract
The use of spanning trees in the compression of data files is studied. A new upper bound for the length of the minimal spanning tree, giving the size of the compressed file, is derived. A special front compression technique is proposed for unordered files. The space demands are compared to an information theoretical lower bound of the file size.
References
[1]
Peter A. Alsberg,Space and time saving through large data base compression and dynamic restructuring, Proc. of the IEEE, Vol. 63, No. 8, August 1975.
[2]
Jon Louis Bentley and Jerome H. Friedman,Fast algorithms for constructing minimal spanning trees in coordinate spaces, IEEE Transactions on Computers, Vol. C-27, No. 2, February 1978.
[3]
H. Blasbalg and R. Van Blerkom,Message Compression, in Data Compression, ed. by Lee D. Davisson and Robert M. Gray (Dowden), Hutchington & Ross, 1976.
[4]
Francis Chin and Davin Houck,Algorithms for updating minimal spanning trees, Journal of Computer and Systems Sciences, Vol. 16, No. 3, June 1978.
[5]
Doron Gottlieb, Steven A. Hagerth, Philippe G. H. Lehot and Henry S. Rabinowitz,A classification of compression methods and their usefulness for a large data processing center, National Computer Conference USA 1975.
[6]
A. N. C. Kang, Richard C. T. Lee, Ching-Liang Chang and Shi-Kuo Chang,Storage reduction through minimal spanning trees and spanning forests, IEEE Transactions on Computers, Vol. C-26, No. 5, May 1977.
[7]
Donald E. Knuth,The Art of Computer Programming, Vol. 1,Fundamental Algorithms, 2nd ed. Addison-Wesley, Reading, MA, 1973.
[8]
Edward M. Reingold, Jurg Nievergelt and Narisngh Deo,Combinatorial Algorithms. Theory and Practice, Prentice-Hall, New Jersey, 1977.
[9]
Daniel J. Rosenkrantz, Richard E. Stearns and Philip M. Lewis II,An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput., Vol. 6, pp. 563–581.
[10]
Ernst J. Schuegraf,A survey of data compression methods for non-numerical records, Canadian Journal of Information Sciences, Vol. 2, No. 1, 1976.
[11]
Richard C. Singleton,Maximum distance q-nary codes, IEEE Trans. Inform. Theory IT-10 (1964).
[12]
V. Kevin and M. Whitney,Algorithm 422 minimal spanning tree H, Collected Algorithms of CACM.
[13]
Gio Wiederhold,Database Design, McGraw-Hill Book Company, NY, 1977.
Index Terms
- Compact storage schemes for formatted files by spanning trees
Index terms have been assigned to the content through auto-classification.
Recommendations
Low-Degree Spanning Trees of Small Weight
Given $n$ points in the plane, the degree-$K$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $K$. This paper addresses the problem of computing low-weight degree-$K$ spanning trees for $K>2$...
Degree-bounded minimum spanning trees
Given n points in the Euclidean plane, the degree-@d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most @d. The problem is NP-hard for 2@__ __@d@__ __3, while the NP-hardness of ...
Node-independent spanning trees in Gaussian networks
Message broadcasting in networks can be efficiently carried over spanning trees. A set of spanning trees in the same network is node independent if two conditions are satisfied. First, all trees are rooted at the same node r. Second, for every node u in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1979 BIT Foundations.
Publisher
BIT Computer Science and Numerical Mathematics
United States
Publication History
Published: 01 December 1979
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Jan 2025
Other Metrics
Citations
Cited By
View all- Ernvall JNevalainen O(1984)Estimating the length of minimal spanning trees in compression of filesBIT10.1007/BF0193451224:1(19-32)Online publication date: 1-Mar-1984