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.
Authors
Additional information
- Category
- Doktoraty, rozprawy habilitacyjne, nostryfikacje
- Type
- praca doktorska pracowników zatrudnionych w PG oraz studentów studium doktoranckiego
- Language
- angielski
- Publication year
- 2006
Source: MOSTWiedzy.pl - publication "Parallel scheduling by graph ranking" link open in new tab
