Methods for general partitioning problem in graphmodels of large-scale systems

Abstract

In a large-scale systems, the decomposition problem should be solved for the efficient analysis of the system. Given a graph model representing a large-scale system, the decomposition problem is transformed into the graph partitioning problem which tries to find vertex cut in the graph. The graph partitioning problem, a well-known combinatorial optimization problem, belongs to a class of NP-complete problems, where no algorithm of polynomial bound is likely to exist. Recently, a general method of solving combinatorial optimization problem has been proposed and applied to various areas, which is called simulated annealing. This thesis investigates whether the simulated annealing method is apropriate to the decomposition problem and present a method based on the simulated annealing for generating a good partition for any graph structure. Contrary to the conventional simulated annealing algorithm, two types of move operators are defined which are selected randomly. The experiments show that the proposed method based on the simulated annealing produces better results compared with the previous method. In addition, various types of graph partitioning such as set partition, general k-way partitioning method, and data dependency graph partitioning are also discussed for the purpose of providing full spectrum of the problem. The set partitioning problem can be considered as an exhaustive case of the graph partitioning problem. Another form of Bell number if formulated which is thought to be more natural than the original one. The general k-way partitioning method is an algorithm modified from the famous Kernighan-Lin 2-way algorithm. the partitioning problem of $k \geq 3$ can be solved with respect to the overall configuration, not the partial configuration as in the recursive 2-way algorithm. The time complexity of the generalized algorithm is $0 (N^2 \cdot \log N)$. Especially, the partitioning problem of the directed graph is discussed in the data dependency graph o...