从消元序和弦图求树分解

Question

我需要一个很好的图的树分解，给定一个消去顺序和一个图的chordalization。在

我的想法是获取图中的所有团（我可以这样做），然后从根开始构建一个二叉树，并根据这些团有多少共同的真实性生成子类（即，团）。我想这样做，直到所有的集团都被利用，因此，我有一棵树。问题是，集团可能有2个以上的顶点，所以我不能递归地为每个顶点运行，树可能不是二元的。在

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

我正在用python做一个实现，目前我有弦图、所有集团的列表和消除顺序。想法和/或代码是非常受欢迎的！在

Answer 1

构造弦图的非尼斯（一般）树分解：找到一个完美的消去序，列举最大团（候选点是一个顶点及其后面出现的邻域），{我把它描述成一个集团的分裂，我用它来描述它的分裂。在

一个nice树分解定义如下（定义来自Daniel Marx）。好的树分解是有根的。每个节点属于四种类型之一。在

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

对不好的树进行任意的根分解，并在根上启动递归转换过程。如果当前节点没有子节点，则构造明显的链，该链由具有引入祖先的叶节点组成。否则，请注意，如果某个顶点至少属于两个子节点，则它属于当前节点。递归地转换子节点和链忘记祖先，直到它们的集合是当前节点的子集为止。理论上最简单的方法是将缺失的元素引入每个子节点，然后集体加入。然而，由于下一步的运行时间通常以指数形式依赖于集合的大小，因此在子集合完成之前尝试一些启发式方法来连接子集合可能是明智的。在