Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie z listy filadelfijskiej
- Opublikowano w:
-
ARS COMBINATORIA
nr 86,
strony 97 - 114,
ISSN: 0381-7032 - Język:
- angielski
- Rok wydania:
- 2008
- Opis bibliograficzny:
- Dereniowski D.: The complexity of list ranking of trees// ARS COMBINATORIA. -Vol. 86., (2008), s.97-114
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 84 razy