The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1

Appendix D. Index to Combinatorial Problems

The purpose of this appendix is to present concise descriptions of the major problems treated in the present book, and to associate each problem description with the name under which it can be found in the main index. Some of these problems can be solved efficiently, while others appear to be very difficult in general although special cases might be easy. No indication of problem complexity is given here.

Combinatorial problems have a chameleon-like tendency to assume many forms. For example, certain properties of graphs and hypergraphs are equivalent to other properties of 0–1 matrices; and an m × n matrix of 0s and 1s can itself be regarded as a Boolean function of its index variables (i, j), with ...