EXACT COLORING ALGORITHM FOR WEIGHTED GRAPHS APPLIED TO TIMETABLING PROBLEMS WITH LECTURES OF DIFFERENT LENGTHS

被引：24

作者：

CANGALOVIC, M ^{[1
]}

SCHREUDER, JAM ^{[1
]}

机构：

[1] UNIV TWENTE, FAC APPL MATH, 7500 AE ENSCHEDE, NETHERLANDS

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1991年 / 51卷 / 02期

关键词：

VERTEX-COLORING; TIMETABLE; GRAPH; INTEGER PROGRAMMING;

D O I：

10.1016/0377-2217(91)90254-S

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

An exact algorithm is presented for determining the interval chromatic number of a weighted graph. The algorithm is based on enumeration and the Branch-and-Bound principle. Computational experiments with the application of the algorithm to random weighted graphs are given. The algorithm and its modifications are used for solving timetabling problems with lectures of different lengths.

引用

页码：248 / 258

页数：11

共 15 条

[1] Aarts E., 1989, STAT NEERL, V43, P31
[2] NEW METHODS TO COLOR THE VERTICES OF A GRAPH
BRELAZ, D
[J]. COMMUNICATIONS OF THE ACM, 1979, 22 (04) : 251 - 256
[3] CHROMATIC SCHEDULING AND CHROMATIC NUMBER PROBLEM
BROWN, JR
[J]. MANAGEMENT SCIENCE SERIES B-APPLICATION, 1972, 19 (04): : 456 - 463
[4] CANGALOVIC M, 1989, THESIS U BELGRADE YU
[5] CLEMENTSON AT, 1983, J OPER RES SOC, V34, P503
[6] de Werra D., 1988, ZOR, Methods and Models of Operations Research, V32, P1, DOI 10.1007/BF01920567
[7] AN INTRODUCTION TO TIMETABLING
DEWERRA, D
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 19 (02) : 151 - 162
[8] COMBINATORIAL OPTIMIZATION PROBLEMS WITH SOFT AND HARD REQUIREMENTS
EISELT, HA
LAPORTE, G
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1987, 38 (09) : 785 - 795
[9] GOLUMBIC M, 1980, ALGORITHMIC GRAPH TH, P203
[10] Karp R. M., 1972, COMPLEXITY COMPUTER, P85

← 1 2 →