Studies on Subgraph and Supergraph Enumeration Algorithms
Masashi Kiyomi · SOKENDAI (Graduate University for Advanced Studies) · 2006
Enumeration is listing all objects that satisfy given properties. We call enumeration of subgraphs of a given graph, such that those subgraphs have specified properties, as subgraph enumeration. Similarly We call enumeration of supergraphs of a given graph as subgraph enumeration. In this thesis, we will consider about subgraph/supergraph enumeration algorithms. In areas such as data mining or statistics, subgraph enumeration and supergraph enumeration play important roles to find frequent patterns or to draw on some rules satisfied by the inputs, etc. We developed two types of algorithms of subgraph/supergraph enumeration for chordal and related graphs; one searches graphs to be enumerated by an edge addition or an edge removal; the other defines a neighbor of searching by a simplicial vertex elimination, which is specific for chordal graphs. The first type 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 to develop both subgraph enumeration algorithms and super graph enumeration algorithms. The second type uses nice properties of simplicial vertices and the fact that we can enumerate cliques in a chordal graph quickly. Using this type of algorithm for chordal subgraph enumeration is faster than doing so using the 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 graph classes. In Chapter 3, we discuss the difficulties of our enumeration problems, and explain the framework of the reverse search method. In Chapter 4, we develop algorithms for our enumeration problems. These algorithms are based on the reverse search method. They are of two types: one defines parents such that the difference between a graph and its parent is exactly one, and the other defines parents such that the parent of a graph is obtained by eliminating a simplicial vertex. And, we conclude the thesis in Chapter 5.