Prelegent: mgr Tytus Pikies (Politechnika Gdańska)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina: 11 grudnia 2018 r., g. 12:30
Streszczenie: Problem kolorowania kosztowego polega na znalezieniu kolorowania wierzchołkowego danego grafu o minimalnym łącznym koszcie dla zadanych kosztów kolorów. Podczas wystąpienia zostanie przedstawiona analiza tego problemu względem ważonych grafów dwudzielnych. Zostaną scharakteryzowane sekwencje kosztów dla których problem jest NP-trudny. Zostanie również przedstawiony wielomianowy algorytm optymalny dla pozostałych przypadków.