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

被引：8

作者：

Furmanczyk, Hanna ^{[1
]}

Kubale, Marek ^{[2
]}

机构：

[1] Univ Gdansk, Inst Informat, Wita Stwosza 57, PL-80952 Gdansk, Poland

[2] Gdansk Univ Technol, Dept Algorithms & Syst Modeling, PL-80233 Gdansk, Poland

来源：

ARCHIVES OF CONTROL SCIENCES | 2015年 / 25卷 / 01期

关键词：

batch scheduling; equitable coloring; semi-equitable coloring; cubic graph;

D O I：

10.1515/acsc-2015-0007

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：109 / 116

页数：8

共 8 条

[1] EQUITABLE COLORING AND THE MAXIMUM DEGREE [J].

CHEN, BL ;

LIH, KW ;

WU, PL .

EUROPEAN JOURNAL OF COMBINATORICS, 1994, 15 (05) :443-447

[2] ON THE INDEPENDENCE NUMBER OF RANDOM CUBIC GRAPHS [J].

FRIEZE, A ;

SUEN, S .

RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (05) :649-664

[3] Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines [J].

Furmanczyk, Hanna ;

Kubale, Marek .

DISCRETE APPLIED MATHEMATICS, 2018, 234 :210-217

[4] On bipartization of cubic graphs by removal of an independent set [J].

Furmanczyk, Hanna ;

Kubale, Marek ;

Radziszowski, Stanislaw .

DISCRETE APPLIED MATHEMATICS, 2016, 209 :115-121

[5] Equitable coloring of corona products of cubic graphs is harder than ordinary coloring [J].

Furmanczyk, Hanna ;

Kubale, Marek .

ARS MATHEMATICA CONTEMPORANEA, 2016, 10 (02) :333-347

[6]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[7] EQUITABLE COLORING [J].

MEYER, W .

AMERICAN MATHEMATICAL MONTHLY, 1973, 80 (08) :920-922

[8]

SKULRATTANAKULCHAI S., 2002, 8TH SCANDINAVIAN WOR, P240

← 1 →