A new look at fault tolerant network routing
Danny Dolev, Joe Halpern, et al.
STOC 1984
The existence of a schedule for a partially ordered set of unit length tasks on m identical processors is known to be NP-complete (J. D. Ullman, NP-complete scheduling problems, J. Comput. System Sci., 10 (1975), 384-393). The problem remains NP-complete even if we restrict the precedence graph to be of height bounded by a constant. (J. K. Lenkstra and A. H. G. Rinnooy Kan, Complexity of scheduling under precedence constraints, Operations Res., 26 (1978), 22-35; D. Dolev and M. K. Warmuth, "Scheduling Flat Graphs," IBM Research Report RJ 3398, 1982). In these NP-completeness proofs the upper bound on the number of available processors varies with the problem instance. We present a polynomial algorithm for the case where the upper bound on the number of available processors and the height of the precedence graph are both constants. © 1984.
Danny Dolev, Joe Halpern, et al.
STOC 1984
Danny Dolev, Ruediger Reischuk, et al.
Journal of the ACM
Danny Bickson, Danny Dolev, et al.
IEEE P2P 2008
Danny Dolev, Rüdiger Reischuk, et al.
PODC 1994