A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs

Details A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs

2001-01-23

arxiv.org/abs/cs/0101021v1

SIAM Journal on Computing, 30(3):838--846, 2000

Computer Science

Data Structures and Algorithms

Scientific paper

We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property pi is called a pi-graph. If pi satisfies certain properties, then an n-node m-edge pi-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most beta(n)+o(beta(n)) bits for any continuous super-additive function beta(n) so that there are at most 2^{beta(n)+o(beta(n))} distinct n-node pi-graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such pi include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from {1, ..., ell_1} for ell_1 <= n; (5) the edges of G are labeled with labels from {1, ..., ell_2} for ell_2 <= m; and (6) each node (respectively, edge) of G has at most ell_3 = O(1) self-loops (respectively, ell_4 = O(1) multiple edges). Moreover, ell_3 and ell_4 are not required to be O(1) for the cases of pi being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes.

Affiliated with

Also associated with

No associations

Rating

A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-2645