Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: semi-equitable coloring

Sortuj według:

Ogranicz wyniki do:

Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

Furmańczyk H., Kubale M.

Archives of Control Sciences

2015

Vol. 25, no. 1

109--116

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.