Dana Angluin, James Aspnes, Rida A. Bazzi, Jiang Chen, David Eisenstat, and Goran Konjevod. Effective storage capacity of labeled graphs. Information and Computation 234:44–56, February 2014. (SSS 2010 special issue). An earlier version appeared in Stabilization, Safety, and Security of Distributed Systems: 12th International Symposium, SSS 2010, New York, NY, USA, September 20--22, 2010. Proceedings, Lecture Notes in Computer Science, volume 6366, Springer-Verlag, September 2010, pp. 573–587, under the title “Storage capacity of labeled graphs.” (Winner, Best Student Paper award.)
We consider the question of how much information can be stored by labeling the vertices of a connected undirected graph G using a constant-size set of labels, when isomorphic labelings are not distinguishable. An exact information-theoretic bound is easily obtained by counting the number of isomorphism classes of labelings of G, which we call the information-theoretic capacity of the graph. More interesting is the effective capacity of members of some class of graphs, the number of states distinguishable by a Turing machine that uses the labeled graph itself in place of the usual linear tape. We show that the effective capacity equals the information-theoretic capacity up to constant factors for trees, random graphs with polynomial edge probabilities, and bounded-degree graphs.
@article{AngluinABCEK2014,
author = {Dana Angluin and James Aspnes and Rida A. Bazzi and Jiang Chen and David Eisenstat and Goran Konjevod},
title = {Effective storage capacity of labeled graphs},
month=feb,
journal={Information and Computation},
year = 2014,
volume=234,
pages={44--56}
}