1962/11/01 by Arthur B. Kahn · 747 citations
Computer Science · Engineering · Mathematics · #Embedded Systems Design Techniques #Manufacturing Process and Optimization #Petri Nets in System Modeling #Sorting #Topological sorting #Computer science #Sorting network #Sorting algorithm #Topology (electrical circuits) #Algorithm #Mathematics #Combinatorics #Directed graph
paper · pdf · doi:10.1145/368996.369025
published in Communications of the ACM 5(11), 558-562 (Association for Computing Machinery)
openalex publication_date 1962/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Topological Sorting is a procedure required for many problems involving analysis of networks. An example of one such problem is PERT. The present paper presents a very general method for obtaining topological order. It permits treatment of larger networks than can be handled on present procedures and achieves this with greater efficiency. Although the procedure can be adapted to any machine, it is discussed in terms of the 7090. A PERT network of 30,000 activities can be ordered in less than one hour of machine time. The method was developed as a byproduct of procedure needed by Westinghouse, Baltimore. It has not been programmed and at present there are no plans to implement it. In regard to the techniques described, Westinghouse's present and anticipated needs are completely served by the Lockheed program, which is in current use.