View article

Graphs are ubiquitous objects in the real world. Especially, enumerating subgraphs of a given graph is a fundamental task in computer science. Since the number of subgraphs can be exponentially larger than the input graph size, it is not practical to list all subgraphs one by one. To overcome the difficulty, we focus on implicit enumeration algorithms. Such an algorithm constructs a decision diagram (DD) representing the set of subgraphs instead of explicitly enumerating the subgraphs. This thesis is devoted to designing some implicit enumeration algorithms. We theoretically estimate their complexity and experimentally confirm their efficiency. In this thesis, we mainly use zero-suppressed binary decision diagrams (ZDDs) as DDs. First, we focus on the evacuation planning problem. For this problem, the existing method was limited to grid graphs. We generalize the definition of convexity of regions and propose an algorithm to enumerate partitioning patterns into such regions for general graphs. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. Second, we move on to the balanced graph partitioning problem. We propose an algorithm to enumerate all the graph partitions such that all the weights of the connected components are at least a specified value. Our algorithm uses not only ZDDs but also ternary decision diagrams (TDDs) and realizes an operation, which seems difficult to be designed only by ZDDs. Experimental results show that the proposed algorithm runs up to tens of times faster than an existing state-of-the-art algorithm. Next, we try to extend the types of subgraphs that can be …