Thema der Dissertation:
Search trees on Graphs Thema der Disputation:
Dynamic Treewidth
Search trees on Graphs Thema der Disputation:
Dynamic Treewidth
Abstract: Treewidth is a graph invariant that measures similarity to a tree. Since its introduction in the 1980's, treewidth has been an important tool in structural graph theory and parametrized complexity. In particular, many graph properties (such as the independence number) can be computed in polynomial time on graphs with bounded treewidth, even when computing them on general graphs is NP-hard. Recently, Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski presented a dynamic treewidth data structure, that is, a data structure that maintains a graph of bounded treewidth, along with certain graph properties, under edge additions and deletions. In this talk, we first give a short introduction to the concept of treewidth, and then discuss Korhonen et al.'s result.
Zeit & Ort
18.11.2024 | 12:00
Seminarraum 005
(Fachbereich Mathematik und Informatik, Takustr. 9, 14195 Berlin)