Logic seminar: Kristina Vuškovic (Leeds) ******CANCELLED************
| Dates: | 8 March 2023 |
|---|
| Times: | 15:15 - 16:15 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff, External researchers, Adults, Alumni, Current University students |
|---|
|
Title: Structure and algorithms
Abstract: In this talk we survey structural characterizations of different hereditary graph classes (i.e. classes closed under deletion of vertices), focusing on their algorithmic consequences. Robertson and Seymour, in their famous Graph Minors Project, elucidated the structure of graph classes that are closed under vertex deletion, and deletion and contraction of edges (i.e. minor-closed). Their structural characterization had far reaching algorithmic consequences. Hereditary graph classes on the other hand are a lot more complex, and a whole new set of tools is needed to understand them structurally and to try to extract efficient algorithms from their structure.
Travel and Contact Information
Find event
Frank Adams 1 (and zoom, link in email)
Alan Turing Building
Manchester
