Referat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu. Jest to prawdopodobnie pierwszy algorytm krawędziowego kolorowania grafów w tym modelu. Rozważania teoretyczne zostały poparte eksperymentami komputerowymi.

Referat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.

Przeszukiwanie grafu pojawiło się jako problem matematyczny ponad 40 lat temu i w najogólniejszej wersji zajmuje się odszukiwaniem jednostki-uciekiniera niezależnie od jego poczynań. Od tamtej pory uzyskano wiele wyników odpowiadających na pytanie o minimalną ilość poszukujących jednostek w różnorodnych modelach, czyli odpowiednią liczbę przeszukiwawczą (ang. serach number) grafu. Popularne warianty problemów przeszukiwania obejmują...

Hipergraf to struktura stanowiąca pewne uogólnienie grafu. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności oraz wskażemy zastosowania.

W pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.