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.

Filip Szlachetka

The k-domination number of a graph is the minimum size of a set X such that every vertex of G is at distance at most k from X. We give a linear-time constant-factor approximation algorithm for the k-domination number in classes of graphs with bounded expansion, which include, for example, proper minor-closed graph classes, proper classes closed under taking topological minors, and classes of graphs that can be drawn on a fixed surface with a bounded number of crossings on each edge.

The algorithm is based on the following approximate min-max characterization. A subset A of vertices of a graph G is d-independent if the distance between each pair of vertices in A is greater than d. Note that the size of the largest 2k-independent set is a lower bound for the k-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k-independent set A and a k-dominating set D such that |D| = O(|A|), and these sets can be found in linear time. For the domination number (k = 1), the assumptions can be relaxed, and the result holds for all graph classes with arrangeability bounded by a constant.

1. Z. Dvořák. Constant-Factor Approximation of the Domination Number in Sparse Graphs (2013).
2. Filip Szlachetka. Constant-Factor Approximation of the Domination Number in Sparse Graphs. slides. (2026).