- Tytuł:
- A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
- Autorzy:
-
Giaro, Krzysztof
Kubale, Marek - Powiązania:
- https://bibliotekanauki.pl/articles/31526308.pdf
- Data publikacji:
- 2020-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
bipartite graph
chromatic sum
cost coloring
NP-completeness
polynomial algorithm - Opis:
- In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n2) time. This extends Jansen’s result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC’97, Lecture Notes in Comput. Sci. 1203 (1997) 25–36] for paths and cycles to subgraphs of biquartic graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 885-891
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł