$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

We wtorek, 3 grudnia 2002 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Maciej ŚLUSAREK

(Instytut Informatyki, UJ)

wygłosi referat pod tytułem:

Wybrane algorytmiczne problemy grafowe ,on-line"

Niektóre algorytmiczne problemy grafowe mogą być rozwiązywane w trybie on-line: graf wejściowy jest podawany jako ciąg wierzchołków, a wartość obliczanej funkcji dla kolejnego wierzchołka zależy wyłącznie od podgrafu indukowanego przez dotychczas wczytane wierzchołki. A zatem obliczana jest natychmiast po wczytaniu wierzchołka, i potem nie może już ulec zmianie. Celem badań w tej dziedzinie jest znajdowanie algorytmów, które znajdują rozwiązanie jak najbliższe optymalnemu, oraz wykazywanie dolnych ograniczeń na jakość otrzymywanych rozwiązań w klasie algorytmów on-line. W referacie przedstawione zostaną rezultaty dla grafów interwałowych i łukowych dotyczące wersji on-line problemu kolorowania oraz problemu pokrycia klikami.

Serdecznie zapraszamy wszystkich chętnych !