Generating Chordal Graphs Included in Given Graphs

Masashi KIYOMI  Takeaki UNO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.2   pp.763-770
Publication Date: 2006/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.2.763
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithm
Keyword: 
chordal graph,  enumeration,  constant time,  

Full Text: PDF(262.4KB)
>>Buy this Article


Summary: 
A chordal graph is a graph which contains no chordless cycle of at least four edges as an induced subgraph. The class of chordal graphs contains many famous graph classes such as trees, interval graphs, and split graphs, and is also a subclass of perfect graphs. In this paper, we address the problem of enumerating all labeled chordal graphs included in a given graph. We think of some variations of this problem. First we introduce an algorithm to enumerate all connected labeled chordal graphs in a complete graph of n vertices. Next, we extend the algorithm to an algorithm to enumerate all labeled chordal graphs in a n-vertices complete graph. Then, we show that we can use, with small changes, these algorithms to generate all (connected or not necessarily connected) labeled chordal graphs in arbitrary graph. All our algorithms are based on reverse search method, and time complexities to generate a chordal graph are O(1), and also O(1) delay. Additionally, we present an algorithm to generate every clique of a given chordal graph in constant time. Using these algorithms we obtain combinatorial Gray code like sequences for these graph structures in which the differences between two consecutive graphs are bounded by a constant size.