Search
Abstract
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.
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie z listy filadelfijskiej
- Published in:
-
ARS COMBINATORIA
no. 86,
pages 97 - 114,
ISSN: 0381-7032 - Language:
- English
- Publication year:
- 2008
- Bibliographic description:
- Dereniowski D.: The complexity of list ranking of trees// ARS COMBINATORIA. -Vol. 86., (2008), s.97-114
- Verified by:
- Gdańsk University of Technology
seen 112 times