EDGE-CHROMATIC SCHEDULING WITH SIMULTANEITY CONSTRAINTS

Authors
DEWERRA D MAHADEV NVR PELED UN
Citation
D. Dewerra et al., EDGE-CHROMATIC SCHEDULING WITH SIMULTANEITY CONSTRAINTS, SIAM journal on discrete mathematics, 6(4), 1993, pp. 631-641
Citations number
9
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
6
Issue
4
Year of publication
1993
Pages
631 - 641
Database
ISI
SICI code
0895-4801(1993)6:4<631:ESWSC>2.0.ZU;2-U
Abstract
An edge-coloring model for some types of scheduling problems is descri bed; 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 cl asses of graphs for which such colorings exist are characterized, and a recognition algorithm is derived.