Enumeration of Perfect Sequences of Chordal Graph

摘要

A graph is chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a chordal graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithm. First, a chordal graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward way to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(l) for each perfect sequence.%長さ4以上のサイクルが必ず弦を持つグラフをコーダルグラフと呼ぶ.コーダルグラフでは,極大クリークの集合からクリーク木と呼ばれる特別な木構造を構築することができる.クリーク木の葉を繰返し取り除くとき，その逆順で与えられる極大クリークの列を完全列という.本論文では完全列の列挙問題を研究する.この問題は統計に応用を持つが，これまでに効率的な列挙アルゴリズムは知られていない.この間題の難しさは2つある.まず与えられたコーダルグラフに対するクリーク木は，一般には1つとは限らない.また，ある完全列が2つ以上のクリーク木から生成されることもある.したがって単純にそれぞれのクリーク木から可能な完全列をすべて生成する方法ではうまくいかない.本論文では，クリーク木を明示的に構成することなく，すべての完全列を列挙するアルゴリズムを提案する.本アルゴリズムはこの問題に対する初めての多項式遅延のアルゴリズムである.特に本アルゴリズムは各完全列を平均的にO（1）時間で生成する.