Abstract

Nr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia uporządkowanego kolorowania, które lepiej modelują wymienione sytuacjepraktyczne. Do tych uogólnień należą uporządkowane kolorowanie grafów obciążonych (co pozwala uwzględnić niejednostkowe czasy trwania poszczególnych operacji) oraz uporządkowane listowe kolorowanie (co pozwala uwzględnić sytuacje, gdy pewne operacje powinny lub nie powinny być realizowane w określonych przedziałach czasowych). Oprócz wymienionych uogólnień badane były również: problem szukania drzew spinających o minimalnym uporządkowanym indeksie chromatycznym oraz problem uporzadkowanego kolorowania łuków grafów skierowanych.

Author (1)