Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Preemptive open shop scheduling can be viewed as an edge coloring problem in a bipartite multigraph. In some applications, restrictions of colors (in particular preassignments) are made for some edges. We give characterizations of graphs where some special preassignments can be embedded in a minimum coloring (number of colors = maximum degree). The case of restricted colorings of trees is shown to be solvable in polynomial time.
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Shu Tezuka
WSC 1991
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences