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

Search

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

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

Cite as

Full text

download paper
downloaded 47 times
Publication version
Accepted or Published Version
License
Creative Commons: CC-BY-NC-ND 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 164 times

Recommended for you

Meta Tags