Chromatic cost coloring of weighted bipartite graphs - Publication - Bridge of Knowledge

Search

Chromatic cost coloring of weighted bipartite graphs

Abstract

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.

Citations

  • 1

    CrossRef

  • 0

    Web of Science

  • 2

    Scopus

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:
Articles
Type:
artykuły w czasopismach
Published in:
APPLIED MATHEMATICS AND COMPUTATION no. 375,
ISSN: 0096-3003
Language:
English
Publication year:
2020
Bibliographic description:
Pikies T., Kubale M.: Chromatic cost coloring of weighted bipartite graphs// APPLIED MATHEMATICS AND COMPUTATION -Vol. 375, (2020), s.125073-
DOI:
Digital Object Identifier (open in new tab) 10.1016/j.amc.2020.125073
Sources of funding:
Verified by:
Gdańsk University of Technology

seen 142 times

Recommended for you

Meta Tags