■ 연사: 권오정 교수(한양대학교)

■ 제목: 언제 그래프가 트리처럼 분해될까?

■ 일시: 2022년 10월 13일(목) 17:00

■ 장소: 종합과학관 A동 317호

■ 초록: 그래프 상의 많은 최적화 문제들은 전체 그래프에 대해서는 다항식 시간의 알고리즘을 주기 어렵지만 그래프가 트리인 경우에는 쉽게 해결할 수 있습니다. 그래프가 트리와 비슷한 정도를 측정해 주는 매개변수인 트리윗쓰(tree-width)에 대해 소개하고 트리에서 적용되는 알고리즘들이 확장되는 것에 소개할 예정입니다. Tree-width와 관련된 다양한 연구 분야들에 대해 알아보도록 하겠습니다. 

■ 문의: (02)3277-6990/ims@ewha.ac.kr