Scheduling problems and mixed graph colorings

by Sotskov, Y.N.; Tanaev, V.S.; Werner, F.


Preprint series: 98-38, Preprints

The paper is published: Optimization, Vol. 51 (3), 2002, 597 - 624.

90B35 Scheduling theory, See also {68M20}
05C15 Chromatic theory of graphs and maps


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

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster