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$
6
  • 1
    $\begingroup$ Have you seen wikipedia page: en.wikipedia.org/wiki/List_of_algorithms#Graph_algorithms $\endgroup$
    – Chandru1
    Sep 14, 2010 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, 2011 at 14:02
  • 2
    $\begingroup$ Are the encodings sought for general graphs or just for trees? Labeled or unlabeled? $\endgroup$
    – Mitch
    Feb 6, 2011 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, 2011 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$ Feb 7, 2011 at 8:10

2 Answers 2

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$
2
  • $\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, 2011 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, 2011 at 17:31
-2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.