Report Number: CS-TR-72-300
Institution: Stanford University, Department of Computer Science
Title: Counterexample to a conjecture of Fujii, Kasami and Ninomiya.
Author: Kaufman, Marc T.
Date: June 1972
Abstract: In a recent paper [1], Fujii, Kasami and Ninomiya presented a
procedure for the optimal scheduling of a system of unit
length tasks represented as a directed acyclic graph on two
identical processors. The authors conjecture that the
algorithm can be extended to the case where more than two
processors are employed. This note presents a counterexample
to that conjecture.
[1] Fujii, M., T. Kasami and K. Ninomiya, "Optimal Sequencing
of Two Equivalent Processors, SIAM J. Appl. Math., Vol. 17,
No.4, July 1969, pp. 784-789.
http://i.stanford.edu/pub/cstr/reports/cs/tr/72/300/CS-TR-72-300.pdf