IEEE Transactions on Computers · 1974 · 201 citations · 9 references
EngineeringComputer ScienceElectrical EngineeringAlgorithmsMicroelectronicsOptimizationElectric CircuitsInterconnect DesignPlacement AlgorithmsPrinted Circuit Boards
The Lee path connection algorithm is probably the most widely used method for finding wire paths on printed circuit boards. It is shown that the original claim of generality for the path cost function is incorrect, and a restriction, called the pathconsistency property, is introduced. The Lee algorithm holds for those path cost functions having this property. Codings for the cells of the grid are proposed which will allow the correct operation of the algorithm under the most general path cost function, using the minimum number of states possible, six states per cell. Then methods for reducing the number of calculations by increasing the number of states are presented.
9
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
An Algorithm for Path Connections and Its Applications
C. Y. Lee · IEEE Transactions on Electronic Computers · 1961 · 1.6K citations
The shortest path through a maze
Elmo Moore · Medical Entomology and Zoology · 1959 · 762 citations