dr hab. Bartłomiej Bosek​
​​​​​​​

czwartek 14:00-15:30, sala 0174

Jest to seminarium magisterskie, którego tematyka dotyczy optymalizacji kombinatorycznej. W szczególności interesują nas następujące tematy:

1. Zaawansowane algorytmy znajdujące skojarzenia w grafach (także dwudzielnych) w przypadkach nieważonych i ważonych krawędzi.
2. Problemy konstruowania on-line skojarzeń w grafach dwudzielnych, AdWords Problem - rozwiązania optymalne, randomizowane.
3. Algorytmiczne aspekty pokrycia uniłańcuchami produktów częściowych porządków.

Strona seminarium na UsosWeb znajduje się tutaj.

Mikołaj Jachowicz

I will present an overview of a fully dynamic algorithm for maintaining an interval graph in three different representations: minimal interval models, PQ-trees, and modular decomposition. Vertex insertions and deletions are performed in linear time.

1. Christophe Crespelle. Fully Dynamic Representations of Interval Graphs (2019).
2. Müller, Spinrad. Incremental Modular Decomposition (1989).
3. Mikołaj Jachowicz. Fully Dynamic Representations of Interval Graphs. slides. (2026).