Algorytmy Grafowe 2010/11
[20.09.2011] Ostateczna lista ocen z uwzględnieniem punktów bounsowych znajduje się tutaj.
[13.09.2011] Listę ocen po kolokwium poprawkowym można znaleźć tutaj.
[06.09.2011] Proponowany termin popraki to 13 września, godz. 10:00, sala EA 209. Prosze o kontakt do dnia 9 września w przypadku kolizji tego terminu z innymi egzaminami. Ewentualna zmiana terminu nastąpi więc do 9 września.
[05.05.2011] Uaktualnioną listę ocen można znaleźć tutaj. Propozycje nieobowiązkowych tematów implementacyjnych (we wszystkich przypadkach wymagamy, aby algorytm był wielomianowy, najlepiej o najniższej znanej złożoności, lub bliskiej optimum tam, gdzie jego uzyskanie jest technicznie bardzo trudne):
  • przepływ o zadanej objętości i minimalnym koszcie (algorytm wielomianowy, tzn. złożoność jest wielomianem w funkcji liczby wierzchołków. Uwaga na algorytmy pseudowielomianowe: wielomianowe wzgledem liczby wierzchołków i sumy (bądź max.) wag krawędzi) (90 pkt.) (rezerwacja: 113815)
  • najliczniejsze skojarzenie w (prostym) grafie dwudzielnym (70 pkt.) (rezerwacja: 113764)
  • najliczniejsze skojarzenie w (prostym) grafie dowolnym (100 pkt.) (rezerwacja: 109327)
  • skojarzenie o maksymalnej sumie wag w obciążonym grafie dwudzielnym (70 pkt.)
  • algorytm 5-kolorowania grafów planarnych (bez sprawdzania planarności) (60pkt.) (rezerwacja: 113765)
  • wyznaczanie "perfect elimination ordering" dla danego grafu cięciwowego; na tej bazie zaprojektowanie jako osobnego algorytmu testu czy podany na wejściu graf jest cięciwowy (30 pkt.)
  • implementacja algorytmu "elimination game" dla zadanego grafu i zadanej kolejności wierzchołków (najwygodniej zrobić łącznie z powyższym) (20 pkt.) (rezerwacja: 113611)
  • (Delta+1)-kolorowanie krawędzi dowolnego grafu prostego (70 pkt.)
  • Delta-kolorowanie krawędzi dwudzielnego multigrafu (tw. Brooksa) (60 pkt.)
Jestem otwarty na sugestie implementacji innych klasycznych algorytmów z teorii grafów (liczba punktów do negocjacji). Obowiązuje rezerwacja tematów, która bedzie na bieżąco odzwierciedlana na liście powyżej. Rezerwacja tematu i braku jego realizacji nie wiąże się z żadnymi negatywnymi konsekwencjami, poza nie otrzymaniem żadnych punktów za częściowo zrealizowaną pracę. Algorytm powinien zostać zintegrowany z biblioteką koala (kod "emailowo" przesyłam na prośbę) oraz należycie przetestowany. Wszędzie tam gdzie to możliwe, nie należy definiować własnych struktur danych, tylko korzystać z tych, które już w bibliotece istnieją - dotyczy to w szczególności klasy `graf'.

Ewentualne kolokwium poprawkowe (o ile będą osoby chętne na jego pisanie) odbędzie się w sesji egzaminacyjnej we wrześniu).
[19.04.2011] Wkrótce umieszczę listę zadań implementacyjnych wraz z liczbą punktów, którą można uzyskać za każde z nich. Przypominam, że ocena końcowa jest obliczana tylko i wyłącznie na podstawie SUMY zdobytych punktów.
[18.04.2011] Oceny po kolokwium można pobrać tutaj. Pole "Seminarium" pozostaje puste w przypadku, gdy nie została do mnie przesłana prezentacja omawiana na seminarium (bardzo prosze o przesyłanie prezentacji). W przypadku niezgodności prosze o email.
[10.04.2011] Przypominam o konieczności przesłania prezentacji (osoby, które tego nie zrobiły są oznaczone * na liście tematów).
[1.04.2011] Kolokwium odbędzie się podczas wykładu 18.04.2011r. Podczas pisania kolokwium nie można korzystać z żadnych materiałów pomocniczych. Obowiązuje materiał z wykładu. Przykładowe kolokwia można znaleźć poniżej.
[25.02.2011] Dodałem kilka nowych tematów. Osoby, które już podjęły decyzję mogą ją zmienić ponownie wysyłając listę preferencji (wówczas jeśli wszystkie wskazane tematy są zajęte, to wybranym pozostaje dotychczasowy temat, natomiast jeśli jeden z nowo wybranych jest wolny, to następuje zmiana tematu i ten poprzednio wybrany wraca do puli wolnych. (Nie wysyłam potwierdzeń zwrotnych - strona jest uaktualniana co najmniej raz dziennie.)
[22.02.2011] Proszę o wybieranie tematów oraz o deklaracje terminów wystąpienia. Wolne tematy oraz wolne terminy są oznaczone poniżej. W przypadku braku deklaracji seminaria rozpoczynają się 4 marca zgodnie z kolejnością tematów na liście.

Terminy seminariów:
Gr.1 (pt.godz. 9:15) Gr.2 (pt.godz. 11:15)
25 luty 2011 - -
4 marzec 2011 27,17,16 3,11,24
11 marzec 2011 - -
18 marzec 2011 32,16, 6,13,wolne
25 marzec 2011 28,10,35,36 31,25,1
1 kwiecień 2011 4,7,21 15,wolne,wolne
8 kwiecień 2011 20,22,34 5,wolne,wolne
15 kwiecień 2011 23,8,12 29, 11, wolne
Legenda: liczby oznaczają numer tematu (patrz lista poniżej)


Tematy seminariów:
(Uwaga: *przy numerze indeksu oznacza, że nie otrzymałem jeszcze prezentacji)

  1. Wyszukiwanie elementów w częściowych porządkach.

    109917
    T. Jacobs, F. Cicalese, E. Laber and M. Molinaro, On the Complexity of Searching in Trees: Average-Case Minimization (2010)

  2. Problem zgrupowania agentów w nieznanym grafie (model rozproszony).

    113687
    A. Dessmark P. Fraigniaud D. Kowalski A. Pelc, Deterministic Rendezvous in Graphs (2006)

  3. Wykrywanie "czarnych dziur" w grafie.

    113624
    P. Flocchini, D. Ilcinkas, N. Santoro, Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens (2008)

  4. Technika "kernelizacji" na podstawie wybranego problemu grafowego.

    113295*
    F.N. Abu-Khzamy, R.L. Collinsy, M.R. Fellowsz, M.A. Langstony, W.H. Sutersy and C.T. Symons, Kernelization Algorithms for the Vertex CoverProblem: Theory and Experiments

  5. Ekspandery.

    136115
    S. Hoory, N. Linial, A. Widgerson, Expander graphs and their applications (2006)

  6. Pogoń za szybkim uciekinierem w grafie.

    113734
    F.V. Fomin, P.A. Golovach, J. Kratochvíl, N. Nisse, K. Suchan, Pursuing a fast robber on a graph (2010)

  7. Strzeżenie podgrafu - gra pomiędzy strażnikami a atakującym.

    113608
    F.V. Fomin, P.A. Golovach, D. Lokshtanov, Guard Games on Graphs: Keep the Intruder Out! (2010)

  8. Drzewa spinające o wielu liściach.

    113652
    N. Alon, F.V. Fomin, G. Gutin, M. Krivelevich, S. Saurabh, Spanning Directed Trees with Many Leaves  (2009)

  9. Parametryzowana złożoność oraz kernelizacja na przykładzie problemu indukowanego regularnego podgrafu.

    113630
    H. Moser, D.M. Thilikos, Parameterized complexity of finding regular induced subgraphs (2009)

  10. Minimalne triangulacje w grafach.

    113818
    P. Heggernes, Minimal triangulations of graphs: A survey (2006)

  11. Algorytm samostabilizujący na przykładzie wybranych problemów grafowych.

    113611
    N. Guellati, H. Kheddouci, A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs (2010)

  12. Szukanie celu w mieście pełnym kłamców.

    113826
    N. Hanusse, E. Kranakis, D. Krizanc, Searching with mobile agents in networks with liars (2004)

  13. Eksploracja zmieniającego się świata.

    113764
    C. Avin, M. Koucký, Z. Lotker, How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) (2008)

  14. Pakowanie ścieżek w grafach kubicznych - uogólnienie problemu skojarzenia.

    113761
    K. Kawarabayashi, H. Matsuda, Y. Oda, K. Ota, Path factors in cubic graphs (2002)

  15. Repotymalizacja na przykładzie problemu komiwojażera.

    113644
    C. Archetti, L. Bertazzi, M.G. Speranza, Reoptimizing the traveling salesman problem (2003)

  16. Poszukiwanie krawędziowo rozłącznych ścieżek w grafach.

    113665
    A. Srinivasan, Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems (1997)

  17. Wierzchołkowo rozłączne ścieżki w grafie.

    113603
    N. Robertson, P.D. Seymour, Graph Minors .XIII. The Disjoint Paths Problem (1995)

  18. Trudny problem: poszukiwanie długich ścieżek w grafie.

    wolny
    D. Karger, R. Motwani and G. D. S. Ramkumar, On approximating the longest path in a graph (1997)

  19. "Cutwidth": stała wartość parametru jako przykład radzenia sobie z trudnym problemem.

    wolny
    D.M. Thilikos, M. Serna, H.L. Bodlaender, Cutwidth I: A linear time fixed parameter algorithm (2005)

  20. Szerokość ścieżkowa grafu: przykład optymalnego algorytmu.

    113740
    K. Suchan, I. Todinca, Pathwidth of Circular-Arc Graphs (2007)

  21. Technika branch-and-bound na przykładzie problemu szerokości drzewiastej grafu (treewidth).

    113623
    V. Gogate, R. Dechter, A complete anytime algorithm for treewidth (2004)

  22. Sumacyjne kolorowanie grafów.

    113631
    M.R. Salavatipour, On sum coloring of graphs (2003)

  23. Uogólnienia pewnych miar i parametrów grafowych dla digrafów.

    113815*
    P. Hunter, S. Kreutzer, Digraph measures: Kelly decompositions, games, and orderings (2008)

  24. Czy k policjantów wystarczy by schwytać złodzieja?

    113784
    G. Hahn, G. MacGillivray, A characterization of k-cop-win graphs and digraphs (2003)

  25. 'Szerokość' grafu skierowanego równoważna pewnej grze na grafie.

    113742
    J. Obdržálek, DAG-width - connectivity measure for directed graphs (2006)

  26. Przeszukiwanie budynku za pomocą robotów.

    113747
    A. Kolling, S. Carpin, Pursuit-Evasion on Trees by Robot Teams (2010)

  27. Uporządkowane kolorowanie krawędzi drzewa - algorytm optymalny.

    113765
    P. de la Torre, R. Greenlaw, A. A. Schäffer, Optimal Edge Ranking of Trees in Polynomial Time (1995)

  28. Wielomianowe problemy dla grafów cięciwowych.

    113758
    F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph (1972)

  29. Optymalne i przybliżone kolorowanie wybranych klas grafów.

    113777*
    A. Gräf, M. Stumpf, G. Weißenfels, On Coloring Unit Disk Graphs (1998)

  30. Algorytmy aproksymacyjne dla wybranych problemów dekompozycji grafów.

    wolny
    H.L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, T. Kloks, Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree (1995)

  31. Algorytmy grające

    109327
    E.D. Demaine, Playing Games with Algorithms: Algorithmic Combinatorial Game Theory (2001)
    Uwaga: powyższa praca jest artykulem przeglądowym: do analizy i prezentacji na seminarium należy wybrać grę/algorytm zawierające elementy teorii grafów.

  32. Teoria gier: punkty równowagi

    113299
    N. Nisan, T. Roughgarden, E. Tardos, V.V. Vazirani, Algorithmic game theory (2007 lub inne wydania)
    Uwaga: z powyższej książki należy opracować fragment zawierający elementy teorii grafów (np. rozdział 7: Graphical Games)

  33. Rozgłaszanie w rozproszonych sieciach komputerowych.

    wolny
    D. Ilcinkas, D.R. Kowalski, A. Pelc, Fast Radio Broadcasting with Advice (2008)

  34. Rozproszona weryfikacja drzew spinających.

    113604
    A. Korman, S. Kutten, Distributed verification of minimum spanning trees (2007)

  35. "Mały świat" - analiza algorytmiczna.

    113610*
    J. Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective (1999)

  36. Drzewa klik - struktura i algorytmy.

    113622
    J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees (1992)

  37. Problemy grafowe w sieciach optycznych.

    wolny
    B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Pérennes, U. Vaccaro, Graph Problems Arising from Wavelength–Routing in All–Optical Networks (1997)

  38. Obsługa połączeń w sieciach.

    wolny
    U. Adamy, Call admission control and on-line interval coloring (2003)

Zasady zaliczenia

Wykłady:

  • Wprowadzenie [pdf]
  • Najkrótsze ścieżki z jednym źródłem [pdf]
  • Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków [pdf]
  • Problem komiwojażera - algorytm optymalny [pdf]
  • Heurystyki dla symetrycznego problemu komiwojażera [pdf]
  • Drzewa spinające, problem komiwojażera dla grafów z nierównością trójkąta [pdf]
  • Drzewa spinające o minimalnej średnicy i minimalnym stopniu [pdf]
  • Cykle Eulera [pdf]
  • Przepływy [pdf]
  • Diagramy Voronoi [pdf]
  • Skojarzenia [pdf]
  • Kolorowanie grafów [pdf]
  • Nieklasyczne modele kolorowania grafów [pdf]

Kolokwia z minionych lat:

  • Termin 1 (2008) [ps]
  • Termin 1 (2007) [ps]
  • Termin 1 (2006) [ps]
  • Termin 2 (2006) [ps]
  • Termin 2 (15.02.2006) [ps]
  • Termin 2 (3.02.2006) [ps]
  • Termin 1 (16.01.2006), gr. 1[ps]
  • Termin 1 (16.01.2006), gr. 2[ps]
  • Termin 1 (7.12.2005), gr. 1[ps]
  • Termin 1 (7.12.2005), gr. 2[ps]
  • Termin 1, gr. 1[pdf]
  • Termin 1, gr. 2[pdf]
  • Termin 2, gr. 1[pdf]
  • Termin 2, gr. 2[pdf]