Chromatic cost coloring of weighted bipartite graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Chromatic cost coloring of weighted bipartite graphs

Abstrakt

Given a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended to a substantial class of infinite sequences. We show that these results on both types of sequences partially transfer to unweighted bipartite graphs.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 1

    Scopus

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ły w czasopismach
Opublikowano w:
APPLIED MATHEMATICS AND COMPUTATION nr 375,
ISSN: 0096-3003
Język:
angielski
Rok wydania:
2020
Opis bibliograficzny:
Pikies T., Kubale M.: Chromatic cost coloring of weighted bipartite graphs// APPLIED MATHEMATICS AND COMPUTATION -Vol. 375, (2020), s.125073-
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.amc.2020.125073
Źródła finansowania:
Weryfikacja:
Politechnika Gdańska

wyświetlono 34 razy

Publikacje, które mogą cię zainteresować

Meta Tagi