Graph embedding problem has long been examined for famous interconnection network topologies as a modeling of processor allocation and simulation between parallel architectures in massively parallel processors. As the network topology becomes more complex and larger, the fault tolerance property rises as an important issue. The star graph interconnection network has been recognized as an attractive topology that possesses rich performance properties for interconnection network such as diameter, fault-tolerance, simple routing algorithm, and so on. In this thesis, we consider ring embedding problems in faulty star graph and its family graphs called the (n, k)-star and clustered-star graphs.
First, we propose a new ring embedding scheme in a faulty star graph. For this embedding, the path transition scheme and the node borrow technique are newly proposed in this thesis. The path transition scheme devotes to simplify fault scenarios in the basic component by analyzing path properties. Meanwhile, the node borrow scheme aims at adjusting the path to tolerate the faults in the special positions such as the entry or the exit node in the basic component. Based on these schemes, we show that a ring of length n! - $2f_\upsilon$ can be found in an n-star provided that the number of faulty nodes, denoted by $f_\upsilon$, is at most n-3. Since a star graph is bipartite, our result is optimal in such worst case that all faulty nodes have the same parities, and also superior to the best previous one which makes a ring of length n! - $4f_\upsilon$ under the same fault condition. Moreover, by extending this result into such case that have both node and edge faults, we can construct a ring of length n! - $2f_\upsilon$ in an n-star with $f_\upsilon$ node faults and $f_\epsilon$ edge faults provided that $f_\upsilon+f_\epsilon$≤n-3.
Second, we examine ring embedding problem in a family of star graphs, called as the (n, k)-star and clustered-star graphs. We newly propose a scheme for finding a ring which contains all nodes, that is Hamiltonian cycle, in the (n, k)-star graph. This can be possible by using the recursive structure in the (n, k)-star graph. In addition, we also examine ring embedding problem in a faulty (n, k)-star graph. We show that there still exists a Hamiltonian cycle in an (n, k)-star graph with at most n-3 faulty edges such that $\sum_{2\leqj\leqk}\mid{F_j}\mid\leqk-2$ and $F_1\leqn-k-1$, where $\mid{F_j}\mid$ denotes the cardinality of a set of faulty $j$-edges in the (n, k)-star graph. Meanwhile, the ring embedding problem in a clustered-star graph is directly applicable from the results in the star graph since the clustered-star graph defined by two parameters n and m, denoted by $CS^m_{n-1}$, is a sub-graph of the star graph $S_n$. Hence, by directly applying the same scheme as in the star graph, we show that a ring of length m(n-1)! - $2f_\upsilon$ can be found in the $CS^m_{n-1}$ provided that the number of faults is totally at most n-4 at nodes only, edges only, or both nodes and edges simultaneously.
These results commonly focus on finding the largest ring embeddable in a family of star graphs. Thus the results in this thesis have a contribution to not only the graph theoretic analysis of cycle properties but also the practical applications that utilize the ring or cycle as the basic underlying topology such as routing or broadcasting in massively parallel processors environment.
대규모 병렬처리 컴퓨팅 환경에서 프로세서들의 연결 구조를 표현하는 상호연결망은 그래프를 통해 모델링 된다. 상호연결망에서의 프로세서 할당이나 다른 연결망의 시뮬레이션 문제는 결국 그래프 상호간의 임베딩 문제로 귀결된다. 따라서 상호연결망으로 잘 알려져 있는 그래프들에 대한 임베딩 결과는 수년간에 걸쳐 널리 연구되어 오고 있다. 대표적인 상호연결망 구조로 널리 알려져 있는 하이퍼큐브는 상호연결망으로서 갖추어야 할 우수한 특성을 보유하고 있는 것으로 잘 알려져 왔으나 최근 새로운 상호연결망으로 제안된 스타그래프가 하이퍼큐브보다 여러가지 특성상 보다 향상된 특성을 갖는 것으로 연구되어 오고 있다. 따라서 본 논문에서는 최근 활발한 연구가 진행되고 있는 스타그래프와 그의 단점을 보완하는 새로운 상호연결망으로 제안된 스타그래프 부류에 속하는 그래프들을 대상으로 링 임베딩 문제를 집중적으로 다룬다.
먼저, 스타그래프를 대상으로 고장허용 링 임베딩에 대한 새로운 연구결과를 제시한다. n차원의 스타그래프가 n-3개 이내의 노드 고장 f개를 갖는 경우에 n! - 2f 크기의 링을 항상 임베딩할 수 있음을 보인다. 또한, 이 결과를 에지의 고장을 갖는 경우로 확장시키면 노드에 발생한 고장의 수 $f_\upsilon$와 에지에서 발생한 고장의 수 $f_\epsilon$의 합이 n-3개 이내인 n차원 스타그래프에서 항상 n! - $2f_\upsilon$ 의 크기를 갖는 링을 임베딩할 수 있음을 보인다. 본 논문에서는 이 문제의 해결을 위해서 스타그래프의 재귀적(recursive) 성질을 이용한 분할기법을 이용하여 최종적인 기본 부스타(sub-star)그래프인 4차원 부스타그래프들로 나누어 처리하게 되며, 기본 부스타그래프에서의 고장을 감내(tolerate)하기 위한 전략으로써 패스 전이(path transition) 기법과 인접 부스타그래프로 부터의 노드 차용(node borrow) 기법을 새롭게 제안하고 있다. 이 결과는 지금까지 알려진 동일한 조건하에서 각각 n! - 4f 및 n! - $4f_\upsilon$의 링을 임베딩하는 최근의 연구결과를 개선한 것이며, 모든 고장 노드가 동일한 패리티를 갖는 특별한 경우에는 최적의 해임을 의미한다. 왜냐하면 스타그래프가 이분(bipartite) 그래프이기 때문이다.
두번째로, 스타그래프 부류에 속하는 (n, k)-스타그래프를 대상으로한 링 임베딩 문제를 고려한다. 먼저, 고장이 없는 경우에 헤밀톤 싸이클을 찾는 알고리즘을 제시한다. 아울러 에지에 고장을 갖는 경우로서 1차원상의 에지와 그 이외의 에지에 존재하는 고장의 수가 각각 n-k-1와 k-2개 이내인 경우에는 에지 고장을 감내할 수 있는 헤밀톤 싸이클이 항상 존재함을 보인다. 링을 임베딩하기 위해서는 고장인 에지들을 모두 제거한 후에도 각 노드에서의 남아 있는 연결 에지의 수가 최소한 두 개 이상은 반드시 존재해야 하므로, 이 결과는 최악의(worst) 경우를 고려할 때 허용할 수 있는 에지 고장의 수에 있어 최적임을 의미한다.
본 논문에서 임베딩의 손님(guest)그래프로 고려한 링(혹은 싸이클)은 여러 병렬 알고리즘의 구현에 필수적으로 이용되는 기본 자료구조일 뿐만 아니라 병렬 컴퓨터에서 널리 이용되는 여러 라우팅 및 방송 알고리즘의 구현에 기초가 되는 하부구조이므로 그래프이론적인 측면에서의 싸이클 특성을 분석한 의의와 더불어 실제 응용분야에서도 활용이 예상되는 연구결과로 평가할 수 있다.
