Seminar: Carla Groenland (Utrecht University)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-carla-groenland-utrecht-university
- Seminar: Carla Groenland (Utrecht University)
- 2022-11-22T16:00:00+01:00
- 2022-11-22T17:00:00+01:00
- When Nov 22, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Online seminar, possible to watch in L0.17 at CWI
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
-
Add event to calendar
iCal
Speaker: Carla Groenland (Utrecht University)
Title:
List Colouring Trees in Logspace
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
A List Colouring instance consists of a graph and for each vertex v in the graph, a list L(v) of colours that it may be coloured with. I will explain some ideas behind our algorithm that decides whether an n-vertex tree admits a list colouring using O(log n) bits of work tape. I will also outline some exciting new parameterized complexity classes that can be described via List Colouring on other classes of graphs (XNLP, XALP, …) via graph width measures (pathwidth, treewidth, …).
This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.
Video:
This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.
Video:
Slides: