Reversing trains: A turn of the century sorting problem
|
Academic Article
individual record
abstract
In this paper we study a reversing train puzzle proposed by Sam Loyd near the turn of the century. We concern ourselves with a version of this puzzle described most recently by A. K. Dewdney in Scientific American. There is a train, locomotive and n cars, that must be entirely reversed using only a short spur line attached to the main track. The efficiency of a solution is determined by summing, for all cars, the total distance moved by each car, where distance is measured in car lengths. We present an O(n 2 log 2 n) algorithm for accomplishing this task. 1989.
authors
publication outlet
Journal of Algorithms
author list (cited authors)
Amato, N., Blum, M., Irani, S., & Rubinfeld, R.
publication date
1989
publisher
Elsevier
Publisher
altmetric score
2.0
citation count
10
identifier
324354SE
Digital Object Identifier (DOI)
start page
413
end page
428
volume
10
issue
3