Combinatorial and Algorithmic Techniques in Graph Theory 🗓 🗺
SPEAKER: Vida Dujmovic
Vida Dujmovic is an Assistant Professor at the School of Computer Science and Electrical Engineering, at the University of Ottawa, Canada. She is also a member of the Computational Geometry Lab which includes members from the University of Ottawa and Carleton University.
Her homepage is here
Her CV can be found here
WHEN
Lecture 1: Wed 24 Feb 2016, 15:00-16:00
Lecture 2: Thu 25 Feb 2016, 15:00-16:00
Lecture 3: Tue 1 Mar 2016, 15:00-16:00
Lecture 4: Wed 2 Mar 2016, 15:00-16:00
WHERE
Sala Riunioni, Primo Piano, Sezione di Informatica e Automazione, Via della Vasca Navale 79/81.
ABSTRACT
Lecture 1 and 2: (Layered) separators and (layered) treewidth
In the first two lectures, I will talk about treewidth and the related notion of graph separators. The class of graphs that have constant treewidth are precisely the graphs whose every subgraph has a constant size separator. Graph separators and treewidth are a ubiquitous tool in graph theory and computer science as they are key to many divide and conquer and dynamic programming algorithms. Treewidth is also a key parameter in the theory of graph minors.
In some applications however, the usefulness of graph separators is limited by the fact that the separator size may not be a constant but it depends on the size of the graph. This is the case for planar graphs, for example, as they can have Omega(sqrt n) separators in graphs with n vertices.
I will then introduce a special type of graph separator, called a layered separator and the closely-related notion of layered treewidth. These separators may have linear size in n, but have constant size with respect to a different measure, called the “width”. I will then present a couple of applications of these layered separators where they helped us make progress on some long-standing open problems.
Lecture 3 and 4: Entropy compression and graph coloring
The Lovasz local lemma is one of the most important and versatile tools
of the so-called probabilistic method. It has found a plethora of applications in graph colouring. A recent breakthrough, dubbed entropy compression, by Moser [STOC 2009], Moser and Tardos [JACM 2010] introduced a simple algorithmic proof of the Lovasz local lemma. It is a simple and powerful method both for designing algorithms and for proving the existence of combinatorial objects.
Subsequent work has shown that entropy compression can help in existence proofs, and can even prove stronger results than those obtained by the local lemma. I will present one such simple result about nonrepetitive colourings. The result improves on the previous result of Alon et al. [Random Structures & Alg. 2002] based on the local lemma.
Some of the results presented here have been obtained in collaboration with: David Eppstein, Fabrizio Frati, Gwenaël Joret, Pat Morin, and David R Wood.
