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

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

Full description

Bibliographic Details
Main Authors:	Furmańczyk Hanna, Kubale Marek
Format:	Article
Language:	English
Published:	Sciendo 2015-03-01
Series:	Archives of Control Sciences
Subjects:	batch scheduling equitable coloring semi-equitable coloring cubic graph
Online Access:	http://www.degruyter.com/view/j/acsc.2015.25.issue-1/acsc-2015-0007/acsc-2015-0007.xml?format=INT

id	doaj-art-1a3189517ccf44df94e24fc5de1ce60d
recordtype	oai_dc
spelling	doaj-art-1a3189517ccf44df94e24fc5de1ce60d2018-09-02T14:29:15ZengSciendoArchives of Control Sciences2300-26112015-03-0125110911610.1515/acsc-2015-0007acsc-2015-0007Equitable and semi-equitable coloring of cubic graphs and its application in batch schedulingFurmańczyk Hanna0Kubale Marek1Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, PolandDepartment of Algorithms and System Modeling, Technical University of Gdańsk, Narutowicza 11/12, 80-233 Gdańsk, PolandIn 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.http://www.degruyter.com/view/j/acsc.2015.25.issue-1/acsc-2015-0007/acsc-2015-0007.xml?format=INTbatch schedulingequitable coloringsemi-equitable coloringcubic graph
institution	Open Data Bank
collection	Open Access Journals
building	Directory of Open Access Journals
language	English
format	Article
author	Furmańczyk Hanna Kubale Marek
spellingShingle	Furmańczyk Hanna Kubale Marek Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling Archives of Control Sciences batch scheduling equitable coloring semi-equitable coloring cubic graph
author_facet	Furmańczyk Hanna Kubale Marek
author_sort	Furmańczyk Hanna
title	Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
title_short	Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
title_full	Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
title_fullStr	Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
title_full_unstemmed	Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
title_sort	equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
publisher	Sciendo
series	Archives of Control Sciences
issn	2300-2611
publishDate	2015-03-01
description	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.
topic	batch scheduling equitable coloring semi-equitable coloring cubic graph
url	http://www.degruyter.com/view/j/acsc.2015.25.issue-1/acsc-2015-0007/acsc-2015-0007.xml?format=INT
_version_	1612638996876230656

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

Similar Items