Aktualności / News > Dydaktyka / Teaching > Historia / History > Chromatyczna Teoria Grafów, lato 12/13
Chromatyczna Teoria Grafów, lato 12/13
Wykład prowadzi dr Konstanty Junosza - Szaniawski
Prezentacje projektów
Każda grupa powinna przygotować krótką (max 10 minut) prezentację na temat swego projektu:
- prezentacja problemu
- bardzo ogólna idea algorytmu
- wyniki testów
Przykładowe grafy do testów można znaleźć tu i tu.
Harmonogram przedmiotu
- 26.02 - spotkanie organizacyjne
- 05.03 - wybór grup i tematów
- 26.03 - dokumentacja wstępna
- 14.05 - kontrola postępu prac
- 28.05 - aplikacja i raport z testów
- 11.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)
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.)
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 lub na wykładzie (będzie ogłoszone)
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.
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 04.06. Po tym terminie student otrzymuje 0 punktów za każdą nieoddaną część.
- W szczególnych usprawiedliwionych przypadkach spóźnienia mogą być rozpatrywane indywidualnie (na korzyść studenta)
- Ostatecznym terminem oddania dowolnej części projektu jest 04.06. Po tym terminie student otrzymuje 0 punktów za każdą nieoddaną część.
- Spotkania mają charakter konsultacyjny - proszę uprzedzić mailem, że chcą Państwo przyjść.
Tematy projektów i propozycje bibliografii
Podane artykuły są propozycjami i można wzorować się na innych lub wymyślić własne algorytmy :).
- L(2,1)-kolorowanie drzew
- 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)
- Kolorowanie grafów euklidesowych
- Graf A., Stumpf M., Weissenfels G.: On Coloring Unit Disk Graphs, Algorithmica, 20, pp. 277-293 (1994)
- 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-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
- 3-kolorowanie grafu
- Beigel R., Eppstein D.: 3-Coloring in time O(1,3446^n): a no-MIS algorithm. 36th IEEE Symposium on Foundations of Computer Science, pp. 444-453 (1995)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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
- 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. 1 pp. 5-15 (2001)
- 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
- Przydział kanałów częstotliwości przez szybką transformację Zeta
- Cygan M, Kowalik Ł.: Channel Assignment via Fast Zeta Transform. arXiv:1103.2275v1
- Przybliżone algorytmy dla liczby achromatycznej drzew
- Krysta P., Loryś K.: Efficient approximation algorithms for the achromatic number. Theoretical Computer Science 361 (2006), pp. 150-171
- [własna propozycja tematu] Acykliczne kolorowanie grafów o ograniczonym stopniu
- Fertin G., Raspaud A.: Acyclic Coloring of Graphs of Maximum Degree Delta. DMTCS proc. AE (2005), pp. 389-396
- [własna propozycja tematu] 2-kolorowanie grafów przecięć geometrycznych
- Eppstein D.: Testing bipartiteness of geometric intersection graphs. ACM Transactions on Algorithms 5 art. 15 (2009)
- [własna propozycja tematu] Ewolucyjny algorytm dla L(2,1)-etykietowania
- Własne propozycje tematów.