사회적거리두기
시행
 
마스크 착용을 생활화하고 불필요한 외출은 삼가해주시기 바랍니다.
※ 기본방역수칙 및 추가 적용 수칙 모두 준수
닫기

서울대 공대 컴퓨터공학부 박근수 교수 연구진, 그래프 동형(Graph Isomorphism) 문제에 대한 세계 최고 성능 알고리즘 기술 개발

작성자 : 관리자|등록일 : 21.01.14|조회수 : 496번 읽음

서울대 공대 컴퓨터공학부 박근수 교수 연구진,
그래프 동형(Graph Isomorphism) 문제에 대한 세계 최고 성능 알고리즘 기술 개발


서울대 공대 컴퓨터공학부 박근수 교수 연구진이 세계 최고 성능의 그래프 동형 알고리즘 기술을 개발하였다. 그래프 동형 문제는 두 개의 그래프가 동형인지 판별하는 문제로 소셜 네트워크 서비스, 생물정보학, 화학정보학 등 다양한 응용 분야에서 그래프 분석을 위해 다루고 있는 핵심 문제이다. Garey & Johnson은 1979년에 NP-complete에 속하는지 혹은 P에 속하는지 알려지지 않은 12개의 미해결 문제를 소개하였는데, 그중에서 그래프 동형 문제는 40년이 지난 현재까지도 미해결 상태로 남아있는 유명한 문제이다.
실용적인 측면에서는 지난 30여 년 동안 nauty/Traces가 그래프 동형 문제를 푸는 가장 빠른 알고리즘으로 알려져 왔다. 박근수 교수 연구진은 그래프 동형 문제를 실제 데이터에서 빠르게 푸는 세계 최고 성능의 알고리즘을 개발하고, 개발한 알고리즘이 benchmark 그래프 데이터에서 nauty/Traces보다 평균 수천 배 빠르게 문제를 푸는 것을 보였다.
개발된 그래프 동형 알고리즘은 공개 SW로 배포되었으며, 이 내용으로 박근수 교수 연구실의 구건모, 남예현 학생이 과학기술정보통신부에서 주최한 ‘2020 공개SW개발자대회’에서 금상을 수상하였다.
박근수 교수 연구진의 그래프 동형 알고리즘에 관한 연구 결과는 ICDE 2021에 accept 되었으며, 2021년 4월에 열리는 ICDE 2021에서 발표될 예정이다.
 
G. Gu, Y. Nam, K. Park, Z. Galil, G.F. Italiano, and W.-S. Han, Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space, International Conference on Data Engineering (ICDE) 2021.

 

이전글 서울대 박용래 교수팀, 센서 하나로 웨어러블 로봇 연구 새 시대 열다
다음글 서울대 공대, 클라우드 활용 확대 위해 KT와 MOU 체결
공과대학소개
교육과정
대학생활
예약신청 및 IT 서비스
온라인강의
소통광장
알림광장