Algorytmy Grafowe

• [20.02.09] Lista ocen (po kolokwium poprawkowym). Termin reklamacji i OSTATNIA (regulaminowa) możliwość oddania projektów to 23.02.2009, godz. 10:00, pok. EA 209.
• [18.02.09] Bieżąca lista ocen znajduje się tutaj.
• [18.02.09] Egzamin poprawkowy odbędzie się 20 lutego, o godz. 12:00 w sali NE 106.
• [18.02.09] Przypominam, że sesja poprawkowa kończy się 20 lutego. W poniedziałek, 23 lutego, następuje zwrot protokołów do dziekanatu, więc będzie to ostatni dzień oddawania zaległych projektów (godzinę ustalimy podczas kolokwium poprawkowego, 20 lutego). Po tym terminie możliwe będzie uzyskanie zaliczenia z mojej strony pod warunkiem, że student spowoduje, że otrzymam odpowiedni protokół z dziekanatu. Najbliższy termin oddania projektów to 20 luty, godz. 14:00 (do godz. 14:30) oraz godz. 17:00 (aż do ostatniego studenta...).
• [07.02.09] Termin kolokwium poprawkowego proponuje na dzień 20 lutego, o godz. 12:00 (czas trwania około 90-100 min.). Sala zostanie podana później. Jeśli termin ten nie jest odpowiedni, to bardzo prosze o kontakt.
• [27.01.09] Wyniki kolokwium znajdują się tutaj. Termin reklamacji: 2.02.2009. W przypadku niezgodności prosze o email. Osoby, które zamierzają poprawiać ocenę proszone są o taką informacje na moj email.
• [12.01.09] Data kolokwium (termin podstawowy): 26.01.2009, godz. 14:15-16:00, sala EA 07.
• [15.10.08] Godziny i terminy referatów zostały ustalone. Osoby, które nie dokonały jeszcze wyboru tematu proszone są o kontakt.

1. Dekompozycja grafu na ścieżki o zadanych długościach.
   wolny
   
   Ming-qing Zhai, Chang-hong Lu, Path Decomposition of Graphs with Given Path Length, Acta Mathematicae Applicatae Sinica, English Series, Vol. 22, No. 4 (2006) 633–638
2. Dekompozycja grafu na maksymalną liczbę cykli.
   106929
   
   Michael Krivelevich, Zeev Nutov, Raphael Yuster, Approximation Algorithms for Cycle Packing Problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, (2005) Vancouver, British Columbia, 556 - 561
3. Ścieżki rozłączne krawędziowo.
   106350
   
   Chandra Chekuri, Sanjeev Khanna, Edge-Disjoint Paths Revisited, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, (2003) Baltimore, Maryland 628-637
4. "Podwójne" pokrycie grafu ścieżkami.
   106290
   
   K. Seyffarth, ChengdeWang, On eulerian and regular perfect path double
   covers of graphs, Discrete Mathematics 293 (2005) 237–250
5. Jednostkowy przepływ pomiędzy zadanymi parami wierzchołków.
   106446
   
   Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd, The All-or-Nothing Multicommodity Flow Problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004) Chicago, IL, USA, 156-165 
6. k-ścieżkowa dekompozycja grafu.
   102049
   
   George Steiner, On the k-path partition of graphs, Theoretical Computer Science 290 (2003) 2147 – 2155
7. Spójne przeszukiwanie grafu.
   106315
   
   Fedor V. Fomin, Dimitrios M. Thilikos, Ioan Todinca, Connected Graph Searching in Outerplanar Graphs, Electronic Notes in Discrete Mathematics 22 (2005) 213–216
8. Niedeterministyczne przeszukiwanie grafów.
   106471
   
   Frederic Mazoita, Nicolas Nisse, Monotonicity of non-deterministic graph searching, Theoretical Computer Science 399 (2008) 169–178
9. Cykliczne czyszczenie grafu.
   106358
   
   M.E. Messinger, R.J. Nowakowski, P. Prałat, Cleaning a network with brushes, Theoretical Computer Science 399 (2008) 191–205
10. Uogólnienia pewnych miar i parametrów grafowych dla digrafów.
    106277
    
    Paul Huntera, Stephan Kreutzer, Digraph measures: Kelly decompositions, games, and orderings, Theoretical Computer Science 399 (2008) 206–219
11. Ograniczone czasowo przeszukiwanie grafu.
    106372, 105001
    
    Brian Alspacha, Danny Dyera, Denis Hansona, Boting Yang, Time constrained graph searching, Theoretical Computer Science 399 (2008) 158–168
12. Wierzchołkowo rozłączne cykle w grafie.
    106319
    
    Alberto Caprara, Romeo Rizzi, Packing triangles in bounded degree graphs, Information Processing Letters 84 (2002) 175–180
13. Problem komiwojażera z macierzą postaci Gilmore-Gomory.
    106259
    
    P.C. Gilmore, R.E. Gomory, Sequencing a one state-variable machine: a solvable case of the traveling salesman problem, Operations Research 12 (1964) 655-679
14. Równoległe szeregowanie zadań z zadanymi konfliktami.
    106393, 106362
    
    Klaus Jansen, The mutual exclusion scheduling problem for permutation and comparability graphs, Information and Computation 180 (2003) 71–81
15. Grafowy model szeregowania wsadowego.
    106367, 106421
    
    Gerd Finke, Vincent Jost, Maurice Queyranne, András Sebo, Batch processing with interval graph compatibilities between tasks, Discrete Applied Mathematics 156 (2008) 556 – 568
16. Szeregowanie zadań wieloprocesorowych na ringu.
    106359, 106427
    
    Giuseppe Confessore, Paolo Dell’Olmo, Stefano Giordani, Complexity and approximation results for scheduling multiprocessor tasks on a ring, Discrete Applied Mathematics 133 (2004) 29–44.
17. Model grafowy dla cyklicznej alokacji rejestrów.
    106466
    
    D. de Werra, Ch. Eisenbeis, S. Lelait, B. Marmol, On a graph-theoretical model for cyclic register allocation, Discrete Applied Mathematics 93 (1999) 191-203
18. Szeregowanie (grup) zadań z relacją poprzedzania.
    106348
    
    Renata Mansini, M. Grazia Speranza, Zsolt Tuza, Scheduling groups of tasks with precedence constraints on three dedicated processors, Discrete Applied Mathematics 134 (2004) 141 – 168
19. Wielokryterialne modele chromatycznego szeregowania zadań.
    106463, 106371
    
    D. de Werra, On a multiconstrained model for chromatic scheduling, Discrete Applied Mathematics 94 (1999) 171-180
20. Przedziałowe kolorowanie grafów.
    wolny
    
    Giuseppe Confessore, Paolo Dell’Olmo, Stefano Giordani, An approximation result for the interval coloring problem on claw-free chordal graphs, Discrete Applied Mathematics 120 (2002) 73–90
21. Model kolorowania dla szeregowania wsadowego.
    106377
    
    D. deWerra, M. Demange, J. Monnot, V.Th. Paschos, A hypocoloring model for batch scheduling, A hypocoloring model for batch scheduling, Discrete Applied Mathematics 146 (2005) 3–26
22. Problem gonitwy i ucieczki - grafowe parametry.
    102199
    
    F.V. Fomin, Helicopter search problems, bandwidth and pathwidth, Discrete Applied Mathematics 85 (1998) 59-70
23. Kolorowanie grafu jako gra.
    106375, 106345
    
    Stephan Dominique Andres, The game chromatic index of forests of maximum degree Delta >= 5, Discrete Applied Mathematics 154 (2006) 1317–1323
24. Strategie powstrzymujące rozprzestrzenianie wirusa.
    106449
    
    A.S. Fraenkel, Virus versus mankind, Lecture Notes In Computer Science 2063 (2000) 204-213
25. Grafowe gry 'cops and robbers'.
    106391, 106369
    
    M. Aigner, M. Fromme, A game of cops and robbers, Discrete Applied Mathematics 8 (1984) 1-12
26. Gra 'Nim' dla grafów.
    wolny
    
    Masahiko Fukuyama, A Nim game played on graphs, Theoretical Computer Science 304 (2003) 387–399
27. Algorytmy w teorii gier (uwaga: jest to szerszy temat zwiazany z teoria gier w ekonomii)
    106391, 106451, 106416
    
    N. Nisan, T. Roughgarden, E. Tardos, V.V. Vazirani, Algorithmic game theory, Cambridge University Press, Cambridge, 2007.
28. Analiza wybranego zagadnienia kombinatorycznych gier na grafach.
    106256
    
    Claude Berge, Combinatorial games on a graph, Discrete Mathematics 151 (1996) 59-65
29. Dynamiczne algorytmy dla przechodniego domknięcia.
    106264
    
    L. Roditty, U. Zwick, Improved dynamic reachability algorithms, SIAM J. Comput. 37 (2008) 1455-1471.
30. Konstrukcja wierzchołkowo rozłącznych ścieżek.
    106286
    
    Tsung-Chi Lin, Dyi-Rong Duh, Constructing vertex–disjoint paths in (n, k)-star graphs, Information Sciences 178 (2008) 788–801

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]