Uporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa o średnicy co najwyżej 4, komety oraz grafy krawędziowe tych klas. Z drugiej strony ścieżki, drzewa o ograniczonej liczbie wierzchołków wewnętrznych to przypadki, dla których opisano algorytmy wielomianowe.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie z listy filadelfijskiej
- Język
- angielski
- Rok wydania
- 2008
Źródło danych: MOSTWiedzy.pl - publikacja "The complexity of list ranking of trees" link otwiera się w nowej karcie
