Fast minimal triangulation algorithm using minimum degree criterion

详细信息    查看全文

• 作者：Mauro Mezzini ; ^a ; ^{mezzini@di.uniroma1.it"" rel=""nofollow}
• 关键词：Minimal triangulations ; Chordal graphs ; Minimum degree
• 刊名：Theoretical Computer Science
• 出版年：2011
• 出版时间：1 July 2011
• 年：2011
• 卷：412
• 期：29
• 页码：3775-3787
• 全文大小：312 K

文摘

We propose an algorithm for minimal triangulation which, using simple and efficient strategy, subdivides the input graph in different, almost non-overlapping, subgraphs. Using the technique of matrix multiplication for saturating the minimal separators, we show that the partition of the graph can be computed in time O(n^α) where n^α is the time required by the binary matrix multiplication. After saturating the minimal separators, the same procedure is recursively applied on each subgraphs. We also present a variant of the algorithm in which the minimum degree criterion is used. In this way, we obtain an algorithm that uses minimum degree criterion and at the same time produces a minimal triangulation, thus shedding new light on the effectiveness of the minimum degree heuristics.