EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 3.0

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

Hanna Furmańczyk, Marek Kubale

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →