Alon Itai, Michael Rodeh
Information and Computation
Given a formulation of a problem, a compact representation is required both for theoretical purposes - measuring the complexity of algorithms, and for practical purposes - data compression. The adjacency lists method for representing graphs is compared to the information theoretic lower bounds, and it is shown to be optimal in many instances. For n-vertex labeled planar graphs the adjacency lists method requires 3 nlog n + O(n) bits, a linear algorithm is presented to obtain a 3/2 nlog n + O(n) representation while nlog n + O(n) is shown to be the minimum. © 1982 Springer-Verlag.
Alon Itai, Michael Rodeh
Information and Computation
Alon Itai, Michael Rodeh, et al.
Theoretical Computer Science
Nadav Eiron, Michael Rodeh, et al.
ACM Journal of Experimental Algorithmics
Alon Itai, Michael Rodeh
Information and Computation