I opened this pdf expecting to see a section on total unimodularity (TU). For example, if an undirected graph is bipartite, its node-edge incidence matrix is T

I opened this pdf expecting to see a section on total unimodularity (TU). For example, if an undirected graph is bipartite, its node-edge incidence matrix is TU. Any linear program operating on a TU matrix is guaranteed to have an integer solution. This means that any integer program can be relaxed to a linear program. Thus, the problems of bipartite matching and maximum flow can be easily solved using Simplex. Some of the interesting results are described here: https://en.wikipedia.org/wiki/Unimodular_matrix#Examples_of_unimodular_matrices https://en.wikipedia.org/wiki/Unimodular_matrix#Examples_of_... That wikipedia page does not do a great job at presenting the optimization connection. These slides are better: http://eaton.math.rpi.edu/faculty/Mitchell/courses/matp6620/notesMATP6620/lecture15/15B_TUbeamer.pdf http://eaton.math.rpi.edu/faculty/Mitchell/courses/matp6620/...