Scheduling Problems and Mixed Graph Colorings

Authors: Sotskov Y.N.¹; Tanaev V.S.¹; Werner F.²

Source: Optimization, Volume 51, Number 3, 1 January 2002 , pp. 597-624(28)

Buy & download fulltext article:

Price: $56.94 plus tax (Refund Policy)

Abstract:

Some scheduling problems induce a mixed graph coloring, i.e., an assignment of positive integers (colors) to vertices of a mixed graph such that, if two vertices are joined by an edge, then their colors have to be different, and if two vertices are joined by an arc, then the color of the startvertex has to be not greater than the color of the endvertex. We discuss some algorithms for coloring the vertices of a mixed graph with a small number t of colors and present computational results for calculating the chromatic number, i.e., the minimal possible value of such a t. We also study the chromatic polynomial of a mixed graph which may be used for calculating the number of feasible schedules.

Keywords: Scheduling; Mixed graph; Vertex coloring; Chromatic polynomial

Document Type: Research article

Affiliations: 1: Institute of Engineering Cybernetics, Surganov St. 6, 220012 Minsk, Belarus 2: Otto-von-Guericke-Universität, Fakultät für Mathematik, PSF 4120, 39016 Magdeburg, Germany

Publication date: 2002-01-01