Computing treedepth

Fernando Sánchez Villaamil (RWTH Aachen)

When: December 2, 2pm

Where: room G2.91b/G215

Abstract

Treedepth is a graph measure closely related to the class of graphs of bounded expansion, a very general class of sparse graphs. We present an exact algorithm to compute a treedepth decomposition of depth t of a graph, if such a decomposition exists, in time 2^O(t^2 log t) * n. Special attention will be given to the insights about treedepth gained from developing the necessary tools needed to proof the correctness of this algorithm. Based on this ideas possible future avenues of research will be discussed.