Wyszukiwarka
Abstrakt
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
Autorzy (2)
Słowa kluczowe
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Archives of Control Sciences
nr 25,
strony 109 - 116,
ISSN: 1230-2384 - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Furmańczyk H., Kubale M.: Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling// Archives of Control Sciences. -Vol. 25., (2015), s.109-116
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 22 razy