Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Archives of Control Sciences · 2015
DOI: 10.1515/acsc-2015-0007 ↗Kurz gefasst
Fachartikel in der Zeitschrift Archives of Control Sciences, 2015. Verfasst von Hanna Furmańczyk und 1 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 3.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Furmańczyk, H., & Kubale, M. (2015). Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling. Archives of Control Sciences. https://doi.org/10.1515/acsc-2015-0007
Vancouver
Furmańczyk H, Kubale M. Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling. Archives of Control Sciences. 2015. doi:10.1515/acsc-2015-0007
BibTeX
@article{Furmaczyk2015,
author = {Furmańczyk, Hanna and Kubale, Marek},
title = {Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling},
journal = {Archives of Control Sciences},
year = {2015},
doi = {10.1515/acsc-2015-0007}
}
EUVIMED