Po uporządkowaniu wiedzy dotyczącej algorytmow grafowych nabytej przez studentów na wykładach obowiązkowych, zagłębimy się w problematykę nieomawianą dotychczas. Szczególny nacisk planuję położyć na klasyczne problemy efektywnie rozwiązywalne w przypadku szczególnych, ważnych podklas grafów. Zestaw zagadnień będzie się systematycznie pojawiał na stronie wykładu. Wszelkie komentarze i sugestie studentów w trakcie tworzenia programu będą mile widziane. Podczas poprzedniej edycji tego wykładu rozważaliśmy m.in. następujące problemy:
* Problem najkrótszych dróg z zadanego źródła; w tym algorytmy:
* Gabowa
* AMOT
* Goldberga
* Thorupa
* Hagerupa
* Algorytm Bendera i Farach-Coltona da problemu LCA
* Weryfikacja MST w czasie liniowym (algorytm King)
* Znajdowanie MSTw oczekiwanym czasie liniowym (algorytm Kargera, Kleina, Tarjana)
* Znajdowane minimalnej arborescencji (algorytm Karpa)
* Przybliżanie grafów za pomocą drzew
* Znajdowanie najkrótszych ścieżek między wszystkimi parami wierzchołków (m.in algorytm Seidel'a)
* Algorytmy dla grafów cięciwowych.
* Algorytmy dla grafów ordynkowych
* Algorytmy dla grafów przedziałowych
* Algorytmy sprawdzania planarności grafów
* Problem kliki dla grafów planarnych
* Separatory dla grafów planarnych
Matematyka Dyskretna
Algorytmy i Struktury Danych
