Algorytmiczna teoria grafów

Tutaj będą prawdopodobnie pojawiać się notatki do niektórych ćwiczeń z algorytmicznej teorii grafów, które porwadzę razem z Maćkiem Kurowskim. Być może będziemy tu umieszczać także linki do tekstów, z których korzystaliśmy.

• (dokładne) 3-kolorowanie wierzchołkowe grafów Eppstein, Beigel "3-coloring in time O(1.3289^n)"
• Grafy planarne: Wzór Eulera, 6-orientacja krawędzi, tw. Tutte, tw. Kuratowskiego. [planarne.ps]
• Skojarzenia w grafie dwudzielnym, kolorowanie stronicowe. [cw2.ps]
• Kolorowanie stronicowe: Diks, Kowalik, Kurowski "A new 3-color criterion for planar graphs". [3col.ps]
• Kolorowanie krawedziowe grafow dwudzielnych w czasie $O(E \log \Delta)$: Cole, Ost, Schirra "Edge-Coloring Bipartite Multigraphs in O(E log D) Time"
• Efektywne algorytmy znajdowania maksymalnego przepływu (algorytm Dinica, algorytm trzech Hindusów). [przeplywy.ps]
• Twierdzenie Mengera [menger.ps]
• Twierdzenie o separatorze w grafach planarnych [separator.ps]

>> Tematy na egzamin
Uwaga ! Spośród 6 tematów należy wybrać 2, co najmniej jeden z grupy 1..3.