Oμιλία του Sebastian Wiederrecht την Τρίτη 08/10/2019 στις 15:00 στην αίθουσα Α56

Tην Τρίτη 08/10/2019 στις 15:00 θα δώσει ομιλία ο Sebastian Wiederrecht στην αίθουσα Α56.
Για τους Μεταπτυχιακούς Φοιτητές του ΠΜΣ "Πληροφορική & Τηλεπικοινωνίες" η διάλεξη θα μετρήσει στις υποχρεώσεις για λήψη διπλώματος.

Τίτλος: What is a directed tree?

Περίληψη: 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.