그래프는 관계성이나 상호작용을 모델링하기 위해 널리 사용되는 기본적인 자료구조로서 오늘날 물류, 화학, 소셜 네트워크 분석 등 다양한 분야에서 사용되고 있다. 그래프와 관련된 문제 중 graph partitioning과 최단 경로 탐색은 주요한 문제이며 이와 관련된 알고리즘은 실세계의 여러 분야의 문제를 해결하는데 활용되고 있다. Graph partitioning은 어떠한 그래프를 특정 기준에 따라 더 작은 부분 그래프로 쪼개는 작업이며 복잡한 그래프를 분석하기 용이하도록 만들 수 있다. 이를 최단 경로 탐색에 활용한다면 크고 복잡한 그래프에 대해서도 최단 경로를 효과적으로 찾을 수 있다. 본 기술문서는 graph partitioning에 대해 다룬다. Graph partitioning를 소개하고, graph partitioning의 두 알고리즘 유형을 간단히 기술한다. 이어서 graph partitioning을 최단 경로 탐색 문제에 적용한 방법을 기술한다.

보고서작성: 고려대학교 정보보호대학원 해킹대응기술연구실 (지도교수 : 김휘강 교수)

DOWNLOAD

• Korean Version (국문): Download

AUTHOR

• 유정도, 박상범, 사공채연, 이재성, 송민근, 최재웅, 김휘강

ACKNOWLEDGEMENT

• This work was supported by Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2021-0-00624, Development of Intelligence Cyber Attack and Defense Analysis Framework for Increasing Security Level of C-ITS)

HISTORY

• Written on 2024-11-30