Zapraszamy na seminarium wydziałowe

W imieniu Dziekana Wydziału serdecznie zapraszamy pracowników oraz studentów na kolejne seminarium wydziałowe, które odbędzie się we wtorek 17 grudnia o godz. 12:30 w Instytucie Informatyki, sala 119.

Prelegentem będzie dr Paweł Gawrychowski z Instytutu Informatyki UWr, autor ponad 100 publikacji z dziedziny algorytmiki, w tym kilku zaprezentowanych na najbardziej prestiżowych konferencjach informatycznych (m. in. STOC 2019), który wygłosi wykład pt.

Struktury danych dla grafów planarnych.

Przed wykładem, o godz. 12:00 Dziekan zaprasza na przedświąteczny poczęstunek.

Streszczenie:
Jednym z podstawowych problemów rozważanych w kontekście algorytmów grafowych jest zbudowanie struktury danych, która umożliwia wyznaczanie odległości między dowolną parą wierzchołków. Jeśli zależy nam na bardzo szybkim przetwarzaniu takich zapytań, ciężko uniknąć konieczności zapamiętania odpowiedzi na wszystkie możliwe pytania bez żadnych dodatkowych założeń dotyczących rozważanego grafu. Klasą grafów, którą można uznać za szczególnie naturalną w kontekście tego problemu ze względu na potencjalne zastosowania, są grafy planarne. Opowiem o najnowszych wynikach dotyczących wyroczni odległości dla grafów planarnych oraz innych zagadnień związanych z odległościami w grafach planarnych, w tym tak zwanych schematów etykietowania, które można traktować jako rozproszony odpowiednik takiej struktury danych.