Studies on Subgraph and Supergraph Enumeration Algorithms

Enumeration is listing all objects that satisfy given properties. We callenumeration of subgraphs of a given graph, such that those subgraphs havespecified properties, as subgraph enumeration. Similarly We call enumerationof supergraphs of a given graph as subgraph enumeration. In this thesis, we willconsider about subgraph/supergraph enumeration algorithms. In areas such asdata mining or statistics, subgraph enumeration and supergraph enumerationplay important roles to find frequent patterns or to draw on some rules satisfiedby the inputs, etc. We developed two types of algorithms of subgraph/supergraph enumerationfor chordal and related graphs; one searches graphs to be enumerated by anedge addition or an edge removal; the other defines a neighbor of searching bya simplicial vertex elimination, which is specific for chordal graphs. The firsttype uses the fact that there are only O(n2) edges in a complete graph Kn,and achieves polynomial time delay algorithms. We can use this method todevelop both subgraph enumeration algorithms and super graph enumerationalgorithms. The second type uses nice properties of simplicial vertices and thefact that we can enumerate cliques in a chordal graph quickly. Using this typeof algorithm for chordal subgraph enumeration is faster than doing so usingthe first type (it needs only constant time to enumerate each chordal graph).However, this method is only for the subgraph enumeration. The organization of this thesis is as follows. We first introduce enumeration,focusing particularly on graph enumeration. Chapter 2 provides the preliminaries,notes about terms that we use in this thesis, and explanations about graphclasses. In Chapter 3, we discuss the difficulties of our enumeration problems,and explain the framework of the reverse search method. In Chapter 4, wedevelop algorithms for our enumeration problems. These algorithms are basedon the reverse search method. They are of two types: one defines parents suchthat the difference between a graph and its parent is exactly one, and the otherdefines parents such that the parent of a graph is obtained by eliminating asimplicial vertex. And, we conclude the thesis in Chapter 5