Search
Abstract
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
Citations
-
7
CrossRef
-
0
Web of Science
-
9
Scopus
Authors (2)
Cite as
Full text
download paper
downloaded 42 times
- Publication version
- Accepted or Published Version
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
Archives of Control Sciences
no. 25,
pages 109 - 116,
ISSN: 1230-2384 - Language:
- English
- Publication year:
- 2015
- Bibliographic description:
- Furmańczyk H., Kubale M.: Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling// Archives of Control Sciences. -Vol. 25., iss. 1 (2015), s.109-116
- DOI:
- Digital Object Identifier (open in new tab) 10.1515/acsc-2015-0007
- Verified by:
- Gdańsk University of Technology
seen 157 times