2
$\begingroup$

Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may represent different MSTs with the same string.

Update: It would be a very good future reference if every one could mention the graph encoding algorithm they know of. You can also provide a link/url to a paper.

As a start:

  1. Prufer Encoding
  2. Huffman Encoding
  3. Succinct Trees
  4. Ultra-succinct Representation of Ordered Trees

Thanks

$\endgroup$

migrated from math.stackexchange.com Feb 6 '11 at 13:17

This question came from our site for people studying math at any level and professionals in related fields.

  • 1
    $\begingroup$ Have you seen wikipedia page: en.wikipedia.org/wiki/List_of_algorithms#Graph_algorithms $\endgroup$ – Chandru1 Sep 14 '10 at 9:46
  • $\begingroup$ I think the phrasing "How many ... are there?" is dangerous. Maybe rephrase to "What are known ...?" or "How to encode minimum spanning trees?" $\endgroup$ – Raphael Feb 6 '11 at 14:02
  • 2
    $\begingroup$ Are the encodings sought for general graphs or just for trees? Labeled or unlabeled? $\endgroup$ – Mitch Feb 6 '11 at 17:09
  • $\begingroup$ Doesn't matter. List the one you know. It'll be a good knowledge base for anyone related to GT research. Thanks $\endgroup$ – user770 Feb 7 '11 at 7:21
  • $\begingroup$ @Sazzad: if you want a general list for graph encodings, is it OK that we make this into a CW? $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 7 '11 at 8:10
2
$\begingroup$

If you have a binary encoding of the vertices of the graph you can represent the edges with the characteristic boolean function $\chi_E$ of the edge set $E$, i.e. $\chi_E(x,y) = 1 \Leftrightarrow$ there is an edge between the vertices encoded by $x$ and $y$. This boolean function can be represented by e.g. Ordered Binary Decision Diagrams.

It is known that this OBDD representation is not larger than classical representations (adjacency matrix or adjacency lists) and for special graph classes (e.g. cographs and interval graphs) the OBDD size is smaller then the explicit representation (Nunkesser,Woelfel: Representation of Graphs by OBDDs). So you can hope that for good structured graphs the implicit representation is better.

In the case of trees I have shown (with the tools from the above paper) that the OBDD size is generally not better than the explicit representation and you can easily construct a tree so that the OBDD size is large.

Algorithms are called symbolic or implicit if they have access to the input graph only by this functional representation and perform functional operations to solve the problem. There is a good PhD thesis from Sawitzki about this topic but it is in german (PDF).

I think this is a kind of heuristical approach because you can't guarantee that there is a good implicit representation of the graph and so a fast symbolic alghorithm. Even if there exist a good implicit representation it is very hard to find this good one.

$\endgroup$
  • $\begingroup$ So, the primary benefit is less space requirement? Will be of great help to compression algorithms, I presume? By, 'have access to input graph' you meant some certain properties of the graph, i.e. whether the graph is connected, total weight etc? $\endgroup$ – user770 Mar 12 '11 at 15:14
  • $\begingroup$ @Sazzad: Yes one benefit is less space requirements and then perhaps faster algorithms. With 'have access to the input graph by this functional representation' I mean that the algorithms have access only e.g. to the OBDD which represents the characteristic function of the edge set. So the algorithm must evaluate the OBDD on input $x$,$y$ to get the information that $x$ and $y$ are adjacent or not. $\endgroup$ – Marc Bury Mar 12 '11 at 17:31
-2
$\begingroup$

If your looking for MST encoding go for S&T Encoding

$\endgroup$
  • 1
    $\begingroup$ Downvoting because I don't think this provides enough context to be understandable. $\endgroup$ – David Eppstein Dec 30 '12 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy