Twin-Width of Graphs

Prelegent(ci)

Colin Geniet

Afiliacja

ENS Paris-Saclay

Termin

14 października 2020 14:00

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

Twin-width is a graph complexity measure based on a notion of width of permutations by Guillemot and Marx [SODA '14]. Twin-width is defined through sequences of d-contractions, which witness that the twin-width is at most d. Notable classes of graphs with bounded twin-width are proper minor-closed graphs, and classes width bounded clique-width. FO model checking is FPT with regards to twin-width, provided that a good contraction sequence is given in the input. This seminar is meant as an introduction to twin-width, going over the basic definitions and results (stability results, characterization through matrices), and presenting the main theorems.

---