Wyszukiwarka
Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.1445
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Discussiones Mathematicae Graph Theory
nr 29,
strony 253 - 261,
ISSN: 1234-3099 - Język:
- angielski
- Rok wydania:
- 2009
- Opis bibliograficzny:
- Dereniowski D.: Minimum vertex ranking spanning tree problem for chordal and proper interval graphs// Discussiones Mathematicae Graph Theory. -Vol. 29., iss. nr 2 (2009), s.253-261
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.1445
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 119 razy