2022년 4월 8일

듬성한 그래프 [2] : 그래프 마이너 구조정리에 대하여
그래프이론

듬성한 그래프 [2] : 그래프 마이너 구조정리에 대하여

권오정
난 연재에서는 듬성한 그래프 모임을 다루는 데 중요한 나무-폭에 대해 알아보았습니다. 나무-폭이 작은 그래프 모임은 기본적인 듬성한 그래프 모임 중 하나로 최대 독립집합 등의 알고리즘 문제들을 다항식 시간에 해결할 수 있음을 보았습니다. 반면, 나무-폭이 큰 그래프에서는 반드시 큰 격자 그래프를 마이너 포함관계로 찾을 수 있다는 격자 그래프 마이너 정리에 대해서도 알아보았습니다. 나무-폭과 관련된 여러 이론이 형성된 배경에는 바그너의 추측이 있습니다. 1970년에 바그너는 그래프 마이너 포함관계와 관련된 흥미로운 추측을 하였습니다.
Read more
HORIZON은 고등과학원이 발간하는 과학전문 웹진으로 최신 과학의 뛰어난 성과들을 전달하고자 합니다.
기존의 미디어에서 전달하지 않은 깊이와 학술적인 논문에서 펼치지 못하는 범위의 영역을 탐사해 보고자 합니다.
02455 서울특별시 동대문구 회기로 85 | Tel. 02-958-3711 | horizon@kias.re.kr