Speaker
Sebastian Wiederrecht (TU Berlin)
Date
08-10-2019, 15:00
Place
A56, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Abstract
Treewidth is a graph invariant generalising acyclicity, or tree-likeness, of graphs in a way that can be used to obtain many nice structural and algorithmic results. The great success of treewidth has inspired many generalisations of its base ideas to other combinatorial structures like hypergraphs, directed graphs and matroids.
We explore the connection between directed treewidth and hypertree-width and give answers to the question in what way directed treewidth generalises acyclicity in digraphs. To do this we provide characterisations of strongly conencted digraphs of directed treewidth one, a class that can be seen as the directed version of trees.