I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number of vertices is less than 20) and degree is upper bounded by 4, such that we can reconstruct the tree form the encoding, decoding is not necessary to be unique but low degeneracy is expected. Currently, I am given the number of vertices at various distance from the root, say $d = [d_1, d_2, ..., d_k]$ where $d_i$ is the number of vertices at distance $i$ from root. However, the number of tree satisfying this condition is very large. I am looking for other representation (as an alternative to $d$) of tree which will be more suitable for reconstruction, may be approximately. I would prefer the representation which is hierarchical in the sense that, first few information are more constrained and informative, and others are gradually less so. For example, here $d_1$ gives complete information on number of nodes at level 1, there is slight degeneracy in constructing level two nodes from $d_2$, etc. My focus is on approximate reconstruction rather than canonical encoding.

  • $\begingroup$ It's quite difficult to provide an answer without knowing what information is available. For example, if the data for these comes from some sort of experiment, only certain kinds of data may be available. I may suggest a representation that uses the ratio of leaves to inner nodes for arbitrary example, but it may be unavailable. $\endgroup$ – David Cummins Oct 4 '13 at 22:26
  • $\begingroup$ @DavidCummins these graphs are molecular graphs. First I need to code a molecule preferably into a single number and then reconstruct, with low degenearcy, the graph from the number. $\endgroup$ – DurgaDatta Oct 5 '13 at 7:39
  • $\begingroup$ What is the problem with, for example, having the vertices of the tree labelled and simply storing the parent of each vertex? $\endgroup$ – Andrew D. King Dec 6 '13 at 1:23
  • $\begingroup$ The representation should be invariant of labeling, and should preferably result in a single real number or vector of dimension at most tree height. $\endgroup$ – DurgaDatta Dec 6 '13 at 5:15
  • $\begingroup$ What do you mean by degeneracy? Did you mean degeneracy in graph theory? In this case degeneracy of tree is one, even if your molecule structure is planar, its degeneracy is five. I think you mean bounded maximum degree not degeneracy. Also what's wrong if you just make a complete binary,... tree. I mean the structure that you already know, then the only information that you need is the number of nodes. $\endgroup$ – Saeed Dec 8 '13 at 13:58

I'm still not sure that I completely understand the problem domain, but here's a few suggestions:

  • The depth of each leaf.
  • The difference between min and max number of children at each depth.
  • The number of leaves below each node.
  • The difference between the depths of the left and right subtrees for an in-order traversal.
  • The weights required to build a Huffman tree of the same structure.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.