Conference paper
Two languages are more informative than one
Ido Dagan, Alon Itai, et al.
ACL 1991
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.
Ido Dagan, Alon Itai, et al.
ACL 1991
Nurit Dor, Michael Rodeh, et al.
PLDI 2003
David Steinberg, Michael Rodeh
IEEE TC
Alon Itai, Michael Rodeh
Journal of Algorithms