Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Sem. Algorytmika

 

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles


Prelegent: Anna Zych-Pawlewicz

2021-03-18 12:15

We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time O(2^{d^2}), which matches the best known parameter dependency in the running time of a static FPT algorithm for computing the treedepth of a graph.