서울대 공대, 그래프 동형 문제 관련 세계 최고 성능 알고리즘 기술 개발
상태바
서울대 공대, 그래프 동형 문제 관련 세계 최고 성능 알고리즘 기술 개발
  • 방제일 기자
  • 승인 2021.01.14 18:12
  • 댓글 0
이 기사를 공유합니다

[테크월드=방제일 기자] 서울대 공대 컴퓨터공학부 박근수 교수 연구진이 세계 최고 성능의 그래프 동형 알고리즘 기술을 개발했다고 밝혔다.

그래프 동형 문제는 두 개의 그래프가 동형인지 판별하는 문제로 소셜 네트워크 서비스, 생물정보학, 화학정보학 등 다양한 응용 분야에서 그래프 분석을 위해 다루고 있는 핵심 문제이다.

Garey & Johnson은 1979년에 NP-complete에 속하는지 혹은 P에 속하는지 알려지지 않은 12개의 미해결 문제를 소개했는데, 그중에서 그래프 동형 문제는 40년이 지난 현재까지도 미해결 상태로 남아있는 유명한 문제이다.

실용적인 측면에서는 지난 30여 년 동안 nauty/Traces가 그래프 동형 문제를 푸는 가장 빠른 알고리즘으로 알려져 왔다. 박근수 교수 연구진은 그래프 동형 문제를 실제 데이터에서 빠르게 푸는 세계 최고 성능의 알고리즘을 개발하고, 개발한 알고리즘이 benchmark 그래프 데이터에서 nauty/Traces보다 평균 수천 배 빠르게 문제를 푸는 것을 보였다

개발된 그래프 동형 알고리즘은 공개 SW로 배포됐으며, 이 내용으로 박근수 교수 연구실의 구건모, 남예현 학생이 과학기술정보통신부에서 주최한 ‘2020 공개SW개발자대회’에서 금상을 수상했다.

박근수 교수 연구진의 그래프 동형 알고리즘에 관한 연구 결과는 2021년 4월에 열리는 ICDE 2021에서 발표될 예정이다.
 


관련기사

댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
0 / 400
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.