Getting tree decomposition from ordering ordering and chordal graph

Question

I need a good tree decomposition of the graph, giving the order of exclusion and chordalization of the graph.

My idea is to get all the clicks on the graph (what can I do) and build a binary tree starting from the root and make children (i.e. clicks) depending on how many verification clicks have in common. I want to do this until all the clicks are used, and therefore I have a tree. The problem is that clicks can have more than two vertices, so I cannot run recursively for each vertex, since then the tree may not be binary.

http://en.wikipedia.org/wiki/Tree_decomposition http://en.wikipedia.org/wiki/Chordal_graph

I am implementing an implementation in python, and currently I have a chordal graph, a list of all clicks, and a sort order. Ideas and / or code are more than welcome!

Answer 1

To build a fuzzy (generally) tree-like decomposition of a chordal graph: find the ideal ordering order, list the maximum clicks (the candidates are the vertex and the neighboring ones that appear after it in ordering order), use each click as a node decomposition and connect it to the next click in the order of its intersection. I did not describe it completely correctly; see my next answer .

The decomposition of a beautiful tree is defined as follows (definition from Daniel Marx ). Good tree decomposition is rooted. Each node has one of four types.

Leaf (no children): a set {v} Introduce (exactly one child): a set S union {v} with child S (v not in S) Forget (exactly one child): a set S with child S union {v} (v not in S) Join (exactly two children): a set S with children S and S 

Correct the fuzzy tree decomposition arbitrarily and start the recursive transformation procedure at the root. If the current node has no children, then build an obvious chain consisting of a node sheet with an introduction of the ancestors. Otherwise, we note that if any vertex belongs to at least two children, then it belongs to the current node value. Recursively transform children and chain forget ancestors until their sets are subsets of the current node. The easiest way to continue in theory is to introduce the missing elements to each child, and then unite in mass. Since the execution time of the next step, however, often depends exponentially on the given size, it may be wise to try some heuristics to join the children before completing their subsets.