Publications [#237139] of Susan H. Rodger

Conference articles OFFICIALLY ACCEPTED

1. Frederickson, GN; Rodger, SH, NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines, SIAM Journal on Computing, vol. 23 no. 1 (January, 1994), pp. 185-211, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/01/19)

   Abstract:
   The problem of scheduling n unit-time jobs with real-valued release times and deadlines is shown to be in NC. The solution is based on characterizations of a canonical schedule and best subset of jobs to be scheduled in a given time interval. The algorithm runs on a CREW PRAM in O((log n)² time and uses O(n⁴/log n) processors.