Ostatnia aktualizacja:
November 17. 2017 22:47:27
Aktualności / News > Dydaktyka / Teaching > Historia / History > Chromatyczna Teoria Grafów, lato 10/11

Chromatyczna Teoria Grafów, lato 10/11


Wykład prowadzi dr Konstanty Junosza - Szaniawski

Wyniki

Harmonogram przedmiotu

  1. 26.02 - spotkanie organizacyjne
  2. 05.03 - wybór grup i tematów
  3. 26.03 - dokumentacja wstępna
  4. 14.05 - kontrola postępu prac
  5. 28.05 - aplikacja i raport z testów
  6. 04.06 - prezentacja

Warunki oceniania

Studenci przygotowują projekty w zespołach dwu-trzyosobowych.
Z projektu można uzyskać 40 punktów.
Na projekt składa się:

1. Dokumentacja wstępna (9 punktów)
- opis problemu
- sformalizowanie problemu
- projekt algorytmów (pseudokod)
- analiza algorytmów (złożoność, poprawność)
- literatura

2. Aplikacja + przykłady do testów (17 punktów)
Podczas kontroli postępu prac należy pokazać aktualny stan aplikacji. Ma on wpływ na ocenę za aplikację.
Oprócz działającej aplikacji należy przestawić:
- opis zmian w stosunku do dokumentacji wstępnej (jeśli zmienił się algorytm, należy przedstawić jego analizę!)
- krótką instrukcję użytkownika
- zapisane przykłady do testów, gotowe do uruchomienia w aplikacji
Przykłady powinny być zróżnicowane i ilustrować zachowanie algorytmu w różnych przypadkach.
Ocenie podlega m.in. łatwość testowania aplikacji!

3. Raport z testów (9 punktów)
- opis przeprowadzonych testów (wydajność, jakość aproksymacji itp.)
- wyniki testów (w porównaniu z szacunkami)
- wnioski

4. Prezentacja problemu i aplikacji (5 punktów)
- na ostatnich zajęciach prezentacja projektu

Uwagi:
- Warunkiem zaliczenia projektu jest uzyskanie ponad 20 punktów.
- Zaliczenie projektu jest obowiązkowe do zaliczenia przedmiotu (ocena z projektu stanowi 0.4 oceny z przedmiotu)
- Harmonogram może ulec niewielkim zmianom.
- Warunkiem koniecznym do uzyskania punktów za raport z testów i prezentację jest oddanie aplikacji.
- Każdy rozpoczęty tydzień spóźnienia z dowolną częścią to -5 pkt z ogólnej liczby punktów za projekt.
- W szczególnych usprawiedliwionych przypadkach spóźnienia mogą być rozpatrywane indywidualnie (na korzyść studenta)
- Ostatecznym terminem oddania dowolnej części projektu jest 06.06. Po tym terminie student otrzymuje 0 punktów za każdą nieoddaną część.
- Zajęcia nie mają wyznaczonego w planie terminu. Na prezentację lub oddanie poszczególnych części należy umówić się mailem. Pozostałe spotkania mają charakter konsultacyjny - na nie także umawiamy się mailem.

Tematy projektów i propozycje bibliografii

Podane artykuły są propozycjami i można wzorować się na innych lub wymyślić własne algorytmy :).
  1. L(2,1)-kolorowanie drzew
    • Chang G.J., Kuo D.: The L(2, 1)-labeling problem on graphs. SIAM Journal Discrete Mathematics, 9, 309–316 (1996)
    • Hasunuma T., Ishii T., Ono H., Uno Y.: A linear time algorithm for L(2,1)-labeling of trees, Lecture Notes in Computer Science 5757, Algorithms - ESA 2009, 17th Annual European Symposium, Proceedings, Copenhagen, Denmark, pp. 35--46 (2009)
  2. Kolorowanie grafów euklidesowych
    • Graf A., Stumpf M., Weissenfels G.: On Coloring Unit Disk Graphs, Algorithmica, 20, pp. 277-293 (1994)
  3. Problem przydziału kanałów częstotliwości
    • Kral D., An exact algorithm for the channel assignment problem, Discrete Applied Mathematics - Structural decompositions, width parameters and graph labelings (DAS 5) vol 145 issue 2 (2005)
  4. 4-L(2,1)-kolorowanie grafu
    • Havet, F., Klazar, M., Kratochvil, J., Kratsch, D., Liedloff, M.: Exact Algorithms for L(2,1)-Labeling od Graphs. Algorithmica DOI 10.1007/s00453-009-9302-7
  5. 3-kolorowanie grafu
    • Beigel R., Eppstein D.: 3-Coloring in time O(1,3446^n): a n-MIS algorithm. 36th IEEE Symposium on Foundations of Computer Science, pp. 444-453 (1995)
  6. Kolorowanie grafu w czasie 2^n
    • Koivisto M.: An O*(2^n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer , FOCS pp. 583-590 (2006)
  7. Równoległe algorytmy dla kolorowania grafów (należy zaimplementować algorytm równolegle!)
    • Goldberg A., Plotkin S.. Parallel (Delta+1)-coloring of constant-degree graphs, Information Processing Letters, vol. 25 issue 4 pp. 241-245 (1987)
  8. Maksymalne kolorowanie grafu
    • Pemmaraju S.V., Raman R.: Approximation Algorithms for the Max-Coloring Problem, Lecture Notes in Computer Science, vol. 3580/2005 pp. 1064-1075 (2005)
  9. Maksymalne kolorowanie krawędziowe grafu
    • Feng W., Zhang L., Qu W., Wang H.: Approximation algorithm for maximum edge coloring problem. Theoretical Computer Science, vol. 410 issue 11 (2009)
  10. Max-edge-coloring
    • Bourgeois N., Lucarelli G., Milis I., Paschos V.Th.: Approximaring the max-edge-coloring problem. Theoretical Computer Science, vol. 411 issues 34-36, pp. 3055-3067 (2010)
  11. Kolorowanie grafów Euklidesowych z ograniczeniem na odległość.
    • Fiala J., Fishkin A., Fomin F.: On distance contrained labeling of disk graphs. Theoretical Computer Science, vol. 326, issue 1-3 (2004) 
  12. Sprawiedliwe kolorowanie grafów.
    • Kirstead H., Kostochka A., Mydlarz M., Szemeredi E.: A fast algorithm for equitable coloring. Combinatorica, vol. 30 no. 2, pp. 217-224 (2010)
  13. Heurystyczne algorytmy dla T-kolorowania
    • Liu J., Zhong W., Li J.: Multiagent Evolutionary Algorithm for T-coloring Problem. Proceeding SEAL '08. Lecture Notes in Computer Science, vol. 5361, pp. 289-298 (2008)
    • Aicha M., Malika B., Habiba D.: Two hybrid ant algorithms for the general T-colouring problem, International Journal of Bio-Inspired Computation, vol. 2, no.5  pp. 353 - 362 (2010)
  14. Kolorowanie grafu w wielomianowej pamięci.
    • Bodleander H., Kratsch D.: An exact algorithm for graph coloring with polynomial memory. Department of Information and Computing Sciences,Utrecht University Technical Report UU-CS-2006-015
  15. Kolorowanie krawędziowe dwudzielnych mutligrafów.
    • Cole R., Ost K., Schirra S.: Edge-Coloring Bipartite Multigraphs in O ( E log D ) Time. Combinatorica vol. 21 no. 1pp. 5-15 (2001)
  16. Kolorowanie grafów algorytmem mrówkowym
    • Costa D., Hertz A.: Ants can colour graphs. Journal of the Operational Research Society, Volume 48, Number 3, (1997) , pp. 295-305
  17. Przydział kanałów częstotliwości przez szybką transformację Zeta
    • Cygan M, Kowalik Ł.: Channel Assignment via Fast Zeta Transform. arXiv:1103.2275v1
  18. L(2,1)-kolorowanie grafu w czasie O*(3.87^n)
    • Havet, F., Klazar, M., Kratochvil, J., Kratsch, D., Liedloff, M.: Exact Algorithms for L(2,1)-Labeling od Graphs. Algorithmica DOI 10.1007/s00453-009-9302-7
  19. Własne propozycje tematów.