从消除排序和弦图获得一个树分解 [英] Obtaining a tree decomposition from an elimination ordering and chordal graph

问题描述

我需要给予取消订单和图表的chordalization图的一个很好的树分解。

I need a nice tree decomposition of a graph given an elimination ordering and a chordalization of the graph.

我的想法是，以获得在图中（这是我可以做的）所有派系，建立一个二叉树从根开始，让孩子们（即小集团）根据拉帮结派多少veritices的共同点。我想这样做，直到所有派系都使用，因此，我有一棵树。问题是，拉帮结派可以有2个以上的顶点，所以我不能递归地为每个顶点运行的话，树可能不是二进制。

My idea is to obtain all cliques in the graph (which I can do) and build a binary tree starting from a root and make children (i.e., cliques) depending on how many veritices the cliques have in common. I want to do this until all cliques are used and hence, I have a tree. The problem is that the cliques could have more than 2 vertices so I can not recursively run for each vertex as then, the tree might not be binary.

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

我做了一个Python实现，目前我有弦图，所有派系的名单和消除排序。理念，和/或code是无任欢迎！

I am doing an implementation in python and currently I have the chordal graph, a list of all cliques and an elimination ordering. Ideas, and/or code are more than welcome!

推荐答案

<打击>要构建一个弦图的非尼斯（一般）树分解：找到一个完美的淘汰顺序，列举最大派系（考生是一个顶点和邻居后，出现在排序），使用每个集团作为分解节点，并将其连接到下一个集团，它相交的顺序我没有描述的完全正确。看到我的随后的回答。

To construct a non-nice (in general) tree decomposition of a chordal graph: find a perfect elimination ordering, enumerate the maximal cliques (the candidates are a vertex and the neighbors that appear after it in the ordering), use each clique as a decomposition node and connect it to the next clique in the ordering that it intersects. I didn't describe that quite right; see my subsequent answer.

A 不错的树分解定义如下（从的丹尼尔·马克思）。尼斯树分解扎根。每个节点是四种类型之一的

A nice tree decomposition is defined as follows (definition from Daniel Marx). Nice tree decompositions are rooted. Each node is of 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

根不漂亮的树分解随意并开始递归转换过程在根。如果当前节点没有孩子，然后构造明显链，包含引进祖先的叶节点的。否则，观察到，如果一些顶点属于至少两个孩子，那么它属于当前节点。递归转换儿童和链忘​​记祖先直到其集是当前节点的子集。继续在理论上最简单的方法是引入缺少的元素，每一个孩子，然后再加入集体。由于下一步的运行时间，但是，往往成倍取决于设置的大小，它可能是明智的尝试一些启发式的加盟孩子之前自己的子集完成。

Root the non-nice tree decomposition arbitrarily and start a recursive conversion procedure at the root. If the current node has no children, then construct the obvious chain consisting of a leaf node with introduce ancestors. Otherwise, observe that, if some vertex belongs to at least two children, then it belongs to the current node. Recursively convert the children and chain forget ancestors until their sets are subsets of the current node's. The easiest way to proceed in theory is to introduce the missing elements to each child, then join en masse. Since the running time of the next step, however, often depends exponentially on the set size, it might be wise to try some heuristics to join children before their subsets are complete.

这篇关于从消除排序和弦图获得一个树分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！