지연 시간 제한과 가격을 고려한 네트워크 오버레이 설계에 관하여 = On the Network Overlay Design with Delay Constraint and Cost

국문 초록 (Abstract)

사기관이 공용 통신망의 회선을 임차하여 사용 통신망을 구축하고자 할 때, 종종 몇가지 다른 종류의 회선들을 각기 다른 가격에 선택할 수 있게 된다. 일반적으로 빠른(짧은 지연시간을 갖는) 회선은 느린(긴 지연시간을 갖는) 회선에 비해 고가가 된다. 또한 종단 지연 시간에 대한 제약때문에 무조건 저가의 느린 회선들 말을 선택할 수 없게 된다. 결국 사기관의 통신망을 위한 통로를 공용 통신망 위에 덮어 씨워 구축하는 것은 두 개의 상반된 인자인 가격과 속도의 조절에 달려있다. 최소거리 찾기 문제의 변형으로써 다음 문제는 이러한 맥락에서 관심을 갖게 한다: 주어진 종단 지연시간의 한계내에서 두 개의 지점을 잇는 최소비용의 통로는 무엇인가? 이 문제의 해결을 위해 문제를 최소거리 찾기 문제와 색지정 문제를 포함하는 그래프 문제로 정형화시켜 보았다. 일반적으로 이 문제는 NP-complete임을 보였고, 특별한 구조를 갖는 통신망에서 근사 알고리즘을 제시하였다.

목차 (Table of Contents)

• < 요약 >
• 1. 서론
• 2. 문제 정의
• 3. 복잡도 결과
• 4. 나무구조 그래프상의 근사 알고리즘
• 5. 그물 구조를 갖는 그래프의 수치 분석에 관하여
• 6. 결론
• 7. 참고문헌