Minimum vertex ranking spanning tree problem for chordal and proper interval graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

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

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., nr. 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 13 razy

Publikacje, które mogą cię zainteresować

Meta Tagi