Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Tuesday, November 17, 2015, 12:15 pm

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Luis Barba (Carleton University / Université Libre de Bruxelles)

In this talk, we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a $C$-colorable graph undergoing four types of updates: (i) delete an edge; (ii) insert an edge; (iii) delete a vertex and all incident edges; or (iv) insert a vertex with a set of incident edges. We assume that all updates keep the graph $C$-colorable and that $N$ is the maximum number of vertices in the graph at any point in time.

We present two algorithms to maintain an approximation of the optimal coloring that, together, present a trade-off between the number of vertex recolorings and the number of colors used to color the graph: For any $d>0$, the first algorithm maintains a proper $O(C d N^{1/d})$-coloring and recolors at most $O(d)$ vertices per update. The second maintains an $O(C d)$-coloring using $O(dN^{1/d})$ recolorings per update. Both algorithms achieve the same asymptotic performance when $d = \log N$.

Moreover, we show that for any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices, there is a sequence of $m$ updates on a specific graph that forces this algorithm to recolor at least $\Omega(m\cdot N^\frac{2}{c(c-1)})$ vertices.

This is joint work with Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen and Sander Verdonschot.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login