The complexity of list ranking of trees - Publikacja - MOST Wiedzy

Wyszukiwarka

The complexity of list ranking of trees

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 79 razy

Publikacje, które mogą cię zainteresować

Meta Tagi