W pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania. W niniejszym artykule dowodzimy NP-zupełność w przypadku klasy grafów cięciwowych i stałej liczby kolorów równej 3. Oszacowanie to jest najlepszym możliwym. Z drugiej strony pokazujemy, że problem optymalizacyjny można rozwiązać w liniowym czasie dla właściwych grafów przedziałowych.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.7151/dmgt.1445
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Język
- angielski
- Rok wydania
- 2009
