Speaker: Carla Groenland (Utrecht University)
Title: List Colouring Trees in Logspace
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.
Dutch Seminar on Optimization (online series) with Carla Groenland (Utrecht University)
The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events. The next talk is given by Carla Groenland (Utrecht University), with title: List Colouring Trees in Logspace.
Share this page
When
22 Nov 2022
from 4 p.m.
to 22 Nov 2022 5 p.m.
CET (GMT+0100)
Where
Online seminar, possible to watch in L0.17 at CWI
Web
Add
