In this thesis, computational structures applicable to graph problems and tree problems have been established and are used to develop parallel algorithms for typical graphs and trees.
A breadth first search algorithm for general graphs and a depth first search algorithm for acyclic digraphs have been developed. These algorithms which are based on the shortest path algorithm by Dekel et al. runs in $O(\log^2n)$ time using $O(n^3)$ processors where d and n are the diameter and the number of vertices of graphs, respectively. Our breadth first search algorithm turned out to be the same as that of Ghosh and Bhattacharjee which is based on the parallel breadth first algorithm for trees. Maximum matching algorithm for bipartite graphs which runs in O(n*log n*log log n) time using $O(N^2*[n/log n])$ also has been developed.
For tree problems, we have developed algorithms for tree orientation, for maximum matching, and for finding the diameter and the center of trees. These algorithms have the time complexity $O(log^2n)$ using O(n) processors.
For maximum matchings in bipartite graphs, we were able to lower the time bound by using more processors. For other problems, a lower time bound is also achieved using fewer processors.
본 논문에서는 그래프 문제의 병렬계산에 적합한 계산구조를 중심으로, 이를 적용할 수 있는 병렬 그래프 알고리즘들에 관해 연구하였다. 계산 구조라 함은 자료 구조와 이를 다루는 알고리즘, 그리고 자원의 할당을 일컫는 말이다. 여기서 제시한 알고리즘들은 그래프를 위한 것과 그래프의 특수한 경우인 나무를 위한 알고리즘으로 나눌 수 있다.
먼저 그래프에 관한 것으로는 일반 그래프에서의 breadth first search, 순환(cycle)이 없는 방향 그래프에서의 depth first search, 그리고 bipartite 그래프에서의 최다 짝짓기(maximum matching)를 위한 알고리즘을 개발하였다. 그래프의 verter 수와 지름을 각각 n과 d로 나타낼 때, 앞의 두 알고리즘은
O(log d*log n)의 시간 복잡도를 가지며 나머지 알고리즘은
O(n*log n*loglog n)의 시간을 요하고, 이들은 모두 O(n*n/log n)의 processor를 사용한다. 이들은 Dekel 등이 perfect shuffle computer model과 cube connected computer model에서 제시한 최단 거리 알고리즘을 기초로 개발되었다. Breadth first search 알고리즘은 Ghosh 등에 의해 이미 개발된 것과 같은 결과를 얻었으나 그들은 나무에서의 breadth first search 알고리즘을 사용하였으며 본 논문에서는 최단 거리 알고리즘을 적용하였다.
나무를 위한 알고리즘으로는, 나무를 뿌리 나무(rooted tree)로 변환하는 알고리즘 외에 나무에서의 최다 짝짓기, 지름, 그리고 나무의 중심을 구하는 알고리즘을 제시하였다. 이들 알고리즘은 모두 같은 계산구조를 적용하여 개발되었으며 0(log n)의 시간과 0(n)의 processor를 사용한다.
일반 그래프에서의 breadth first search의 경우에는 기존의 연구와 알고리즘의 도입 방법은 다르나 같은 결과에 도달하였고, 순환이 없는 방향 그래프에서의 depth first seareh와 bipartite 그래프에서의 최다 짝짓기 문제에선 보다 많은 processor를 사용함으로써 시간을 줄일 수 있었다. 그 외의 알고리즘에서는 시간과 함께 사용한 processor 수도 크게 감소되었다.
