- Tytuł:
- Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
- Autorzy:
-
Furmańczyk, H.
Kubale, M. - Powiązania:
- https://bibliotekanauki.pl/articles/230004.pdf
- Data publikacji:
- 2015
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Tematy:
-
batch scheduling
equitable coloring
semi-equitable coloring
cubic graph - Opis:
- In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.
- Źródło:
-
Archives of Control Sciences; 2015, 25, 1; 109-116
1230-2384 - Pojawia się w:
- Archives of Control Sciences
- Dostawca treści:
- Biblioteka Nauki
Artykuł