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.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.amc.2020.125073
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach
- Language
- angielski
- Publication year
- 2020
