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 ≥ 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 · log N)$. Especially, the partitioning problem of the directed graph is discussed in the data dependency graph of the AND/OR process model. From the partition concept in the data dependency graph, it is shown that the operation of the AND/OR process model can be improved.
대규모 시스템의 효율적인 분석을 위하여서 분해 문제 (decomposition problem) 가 선결되어야 한다. 어떤 시스템을 나타내는 그래프 모델이 주어지면 분해 문제는 그 그래프 상에서의 버텍스 컷 (vertex cut) 을 찾는 분할 문제로 바뀐다. 그래프 분할 문제는 고전적으로 잘 알려진 최적화 문제로서, 엔피-컴플리트 (NPcomplete) 에 속한다. 최근 최적화 문제를 해결하기 위한 일반적인 방법의 하나로서 시뮬레이티드 어닐링이 제안되어, 여러 분야에서 응용되어 왔다. 본 논문에서는 이 시뮬레이티드 어닐링 방법을 이용하여 어떠한 구조를 가지는 그래프에서도 좋은 분할 형태를 만드는 알고리듬을 제안하고, 실제 이 알고리듬이 분해 문제를 해결함에 있어 얼마나 적합한 지를 연구하였다. 일반적인 시뮬레이티드 어닐링 방법과는 달리 제안된 알고리듬에서는 두 가지 형태의 변환자 (move operator) 가 정의되고, 그 두 가지 방법은 무작위로 선택되어 현재의 분할 상태를 변환시키기 위해 적용된다. 실제의 실험을 통하여 제안된 알고리듬이 기존의 방법들 보다 좋은 결과를 낸다는 것을 보였다.
또한, 집합 분할, 에지 컷 (edge cut) 을 찾는 일반적 k-분할 방법, 그리고 방향성 그래프에 있어서의 그래프 분할 문제 등을 보편적인 형태의 분할 문제로 다루었다. 집합 분할 문제는 그래프 분할 문제에 있어, 모든 분할 형태를 전부 찾아 보는 방법의 하나로서 볼 수 있다. 기존의 벨 수 (Bell number) 와는 달리 각 분할 형태 내에서의 클러스터 갯수를 기준으로 분할하는 다른 형태의 벨 수를 도출하였다. 일반적 k-분할 방법은 커닝한 (Kernighan) 과 린 (Lin) 의 2-분할 방법을 k로 일반화 시킨 것으로써, 그 시간 복잡도는 반복 횟수가 버텍스 갯수와는 독립적이다라는 가정을 이용하면 $O(N^2·logN)$ 이 된다. 특히, 데이타 의존 그래프 (data dependency graph) 에 있어서의 분할 문제는 논리 프로그램의 병렬 처리 모델인 앤드/오아 (AND/OR) 프로세스 모델에서 다루었다. 앤드/오아 프로세스 모델에서 사용되는 데이타 의존 그래프상에서 독립 관계를 정의하여, 그것을 근거로 한 분할 개념을 이용하였다. 분할 개념을 이용함으로써 앤드/오아 프로세스 모델의 동작 효율이 증가됨을 실제의 데이타 의존 그래프상에서 보였다.