View article

Graph partitioning is important for several applications such as evacuation planning, political redistricting, VLSI design, and so on. Many types of graph partitioning problems are NP-hard, and thus it is difficult to find a good graph partition efficiently. In addition, it is often the case that there are several objective functions and we cannot decide the priority between them clearly. Then it is difficult to define what is the optimal solution. In such a case, it is useful to enumerate some solutions with moderately good objectives. However, there are exponentially many graph partitions in a graph, and thus it is difficult to enumerate such graph partitions efficiently. In this thesis, we study an approach using a zero-suppressed binary decision diagram (ZDD), which is a data structure representing a family of sets in a compressed way. Especially, we focus on two types of graph partitioning problems and propose algorithms to …