Repozytorium publikacji - Politechnika Gdańska

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

• Hanna Furmańczyk link otwiera się w nowej karcie ,
• prof. dr hab. inż. Marek Kubale link otwiera się w nowej karcie