Wyszukiwarka
Abstrakt
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(n^2) 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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
1
Scopus
Autorzy (2)
Cytuj jako
Pełna treść
pobierz publikację
pobrano 71 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2215
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
Discussiones Mathematicae Graph Theory
nr 40,
strony 885 - 891,
ISSN: 1234-3099 - Język:
- angielski
- Rok wydania:
- 2020
- Opis bibliograficzny:
- Giaro K., Kubale M.: A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4// Discussiones Mathematicae Graph Theory -Vol. 40,iss. 3 (2020), s.885-891
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2215
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 191 razy