Department Seminars & Colloquia

Category 학과 Seminar/ Colloquium
Event Colloquium
Title Induced subgraphs and tree decompositions
Abstract Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last couple of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.
Daytime 2023-05-11 (Thu) / 16:15 ~ 17:15 ** 날짜에 유의하세요. **
Place E6-1 1501 Auditorium
Language English
Speaker`s name Maria Chudnovsky
Speakers`s Affiliation Princeton University
Speaker`s homepage
Other information
Hosts Sang-il Oum
URL
담당자
연락처