Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
In a 1987 Scientific American Computer Recreations article, A.K. Dewdney posed the problem of reversing an n-car train on a track with a one-car spur using the minimum amount of work. In that article, Dewdney indicated an algorithm for reversing the train that uses O(n3) work. Shortly thereafter, Amato, Blum, Irani and Rubinfeld (Reversing Trains: A Turn of the Century Sorting Problem, J. Algorithms, Vol. 10, 1989, pp. 413-428) discovered a simple recursive algorithm that requires O(n2logn) work to reverse a train. In this paper, we prove that Amato et al.'s algorithm is optimal up to a constant factor, i.e., we prove that any algorithm for reversing an n-car train in the Dewdney model requires Ω(n2log n) work. © 1990.
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
B.K. Boguraev, Mary S. Neff
HICSS 2000
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory