You are not logged in |
Sparse graphs
- Speaker(s)
- Michał Pilipczuk
- Affiliation
- Instytut Informatyki
- Date
- Jan. 9, 2020, 2:30 p.m.
- Room
- room 2180
- Title in Polish
- Grafy rzadkie
- Seminar
- Colloquium Of MIM
Co to znaczy, że dana sieć połączeń jest rzadka? Próbując odpowiedzieć formalnie na to pozornie niewinne pytanie, przedstawimy krótkie wprowadzenie do Sparsity: teorii klas grafów rzadkich. Jest to młoda i prężnie rozwijająca się gałąź teorii grafów, zajmująca się badaniem strukturalnych metod analizy grafów rzadkich. Metody te mają silne i często zaskakujące zastosowania w algorytmice oraz w teorii modeli skończonych.
What does it mean that a given network is sparse? Starting with an attempt of formally answering this innocently looking question, we will give a brief introduction to Sparsity: the theory of classes of sparse graphs. This young and rapidly developing branch of graph theory focuses on building structural methods for the combinatorial treatment of sparse graphs. These methods have strong and often surprising applications in algorithm design and in finite model theory.
