The art of computer programming. Vol. 4 (3 parts). (English) Zbl 0895.68054

Bonn: Addison Wesley Longman. pt 1: 128 p.; pt 2: 128 p.; pt 3: 129 p. (1998).
Announcement of the author: “Combinatorial Algorithms, in preparation. Present plans are to publish “Volume 4” as three separate subvolumes: Volume 4A, Enumeration and Backtracking 7.1. Boolean techniques (aka bit fiddling) 7.2. Generating all possibilities 7.2.1. Combinatorial generators 7.2.2. Basic backtrack 7.2.3. Efficient backtracking 7.3. Shortest paths Volume 4B, Graph and Network Algorithms 7.4. Graph algorithms 7.4.1. Components and traversal 7.4.2. Special classes of graphs 7.4.3. Expander graphs 7.4.4. Random graphs 7.5. Network algorithms 7.5.1. Distinct representatives 7.5.2. The assignment problem 7.5.3. Network flows 7.5.4. Optimum subtrees 7.5.5. Optimum matching 7.5.6. Optimum orderings 7.6. Independence theory 7.6.1. Independence structures 7.6.2. Efficient matroid algorithms Volume 4C, Optimization and Recursion 7.7. Discrete dynamic programming 7.8. Branch-and-bound techniques 7.9. Herculean tasks (aka NP-hard problems) 7.10. Near-optimization 8. Recursion The material will first appear in beta-test form as fascicles of approximately 128 pages each, issued approximately twice per year beginning in 1999. These fascicles will represent my best attempt to write a comprehensive account, but computer science has grown to the point where I cannot hope to be an authority on all the material covered in these books. Therefore I’ll need feedback from readers in order to prepare the official volumes later.”


68R05 Combinatorics in computer science
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68W10 Parallel algorithms in computer science
90Cxx Mathematical programming