The connectivity problem has been studied for a long time in the field of graph theory. Especially edge augmentation problems have been actively studied because; public organizations can supplement the defects of network nodes by solving them. Since the edge-connectivity of graph denotes edge disjoint paths between two vertex sets in G, adding supplement edges can reduce the congestions of the network which topology is identical to G. Also, it can be applied to physical and virtual network design.
This thesis proposes the regular graph edge augmentation problem and the existence of a polynomial time algorithm which solves this problem. The regular graph edge augmentation problem, unlike other edge augmentation problems which insert minimum edges to meet target edge-connectivity, requires $\frag{\mid{V(G)}\mid}{2}$ more edges and makes the graph G maximum connected in $O(dn^5)$ time. We introduce the Edge Exchange algorithm. This algorithm generates a maximum connected (d+1)-regular graph or a regular graph with the number of its minimum edge cut reduced.
그래프 연결성에 대한 연구는 그래프 이론 분야에서 오래동안 연구되어 왔다. 특별히 에지 증대 문제는 공공 기관이 에지의 추가로 네트워크의 결함을 보완하는 것에 사용될 수 있으므로 활발히 연구되었다. 에지 연결성은 두 개의 vertex 집합 사이의 edge 가 공유되지 않는 경로의 갯수를 의미하기 때문에 새로운 edge를 추가하여 혼잡이 발생되는 노드를 우회할 수 있도록 경로를 추가하여 이전의 그래프 G의 위상을 간직하면서 네트워크 혼잡을 줄일 수 있다. 또한, 그래프 연결성에 대한 연구는 물리적 네트워크의 설계와 가상 네트워크의 설계에도 적용될 수 있다.
본 학위 논문은 정규 그래프의 에지 증대 문제를 제시하며, 이 문제의 polynomial time 알고리즘이 존재함을 증명하였다. 이 정규 그래프에서의 에지 증대 문제는 다른 에지 증대 문제와 다르게 $\frag{\mid{V(G)}\mid}{2}$ 개의 edge를 추가하여 $O(dn^{5})$ 시간 안에 최대 연결성을 가지는 그래프를 찾을 수 있음을 보인다. 또한 이 논문에서는 Edge Exchange 알고리즘을 제시한다. 이 알고리즘은 입력된 그래프를 최대의 연결성을 가지는 (d+1)-정규 그래프를 만들거나 입력된 그래프의 minimum edge cut의 갯수가 줄어든 그래프로 만드는 알고리즘이다.