EDGE-CHROMATIC SCHEDULING WITH SIMULTANEITY CONSTRAINTS

被引：6

作者：

DEWERRA, D

MAHADEV, NVR

PELED, UN

机构：

[1] NORTHEASTERN UNIV,DEPT MATH,BOSTON,MA 02115

[2] UNIV ILLINOIS,DEPT MATH STAT & COMP SCI MC 249,CHICAGO,IL 60607

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1993年 / 6卷 / 04期

关键词：

CHROMATIC SCHEDULING; AUTOMATED PRODUCTION SYSTEM; EDGE-COLORING;

D O I：

10.1137/0406048

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An edge-coloring model for some types of scheduling problems is described; the case is handled where some collections of (nonadjacent) edges are required to have the same color. This corresponds to simultaneity constraints. The complexity of this problem is studied. Next, some classes of graphs for which such colorings exist are characterized, and a recognition algorithm is derived.

引用

页码：631 / 641

页数：11

共 9 条

[1]

Berge C., 1976, GRAPHS HYPERGRAPHS

[2]

DEWERRA D, IN PRESS DISCRETE MA

[3]

DEWERRA D, 1990, JUL P INT C GRAPHS C

[4]

EVEN S., 1979, GRAPH ALGORITHMS

[5]

GAREY MR, 1978, COMPUTERS INTRACTABI

[6]

GROTSCHEL M, 1984, ANN DISCRETE MATH, V21, P325

[7] WEAKLY TRIANGULATED GRAPHS [J].

HAYWARD, RB .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (03) :200-209

[8]

Lovasz L., 1972, DISCRETE MATH, V2, P253, DOI DOI 10.1016/0012-365X(72)90006-4

[9] Non-separable and planar graphs [J].

Whitney, Hassler .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1932, 34 (1-4) :339-362

← 1 →