Seminarium Wydziałowe
Jesteś tutaj: Strona główna
poniedziałek, Grudzień 9, 2019
Dziekan Wydziału serdecznie zaprasza pracowników oraz studentów na
seminarium wydziałowe, które
odbędzie się we wtorek 17 grudnia o godz. 12.30 (Instytut Informatyki, sala 119). Prelegentem będzie
Paweł Gawrychowski z Instytutu Informatyki, który wygłosi wykład pt.
"Struktury danych dla grafów planarnych".
Przed seminarium, 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.
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.
