Search
Abstract
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.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.7151/dmgt.1445
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
Discussiones Mathematicae Graph Theory
no. 29,
pages 253 - 261,
ISSN: 1234-3099 - Language:
- English
- Publication year:
- 2009
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.7151/dmgt.1445
- Verified by:
- Gdańsk University of Technology
seen 88 times