Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Storage Capacity of Labeled Graphs
verfasst von : Dana Angluin, James Aspnes, Rida A. Bazzi, Jiang Chen, David Eisenstat, Goran Konjevod
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.