講演抄録/キーワード |
講演名 |
2008-04-18 11:10
Enumeration of Perfect Sequences of Chordal Graph Yasuko Matsui(Tokai Univ.)・○Ryuhei Uehara(JAIST)・Takeaki Uno(NII) COMP2008-3 |
抄録 |
(和) |
(まだ登録されていません) |
(英) |
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(1) for each perfect sequence. |
キーワード |
(和) |
/ / / / / / / |
(英) |
chordal graph / clique tree / enumeration / perfect sequence / / / / |
文献情報 |
信学技報, vol. 108, no. 11, COMP2008-3, pp. 15-22, 2008年4月. |
資料番号 |
COMP2008-3 |
発行日 |
2008-04-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2008-3 |