Chapter 2: Shortest Paths, Maximal Flows, and Trees
Mustafa Ç. Pınar, Deniz Akkaya · Society for Industrial and Applied Mathematics eBooks · 2023
The problems collected in this chapter are connected to some combinatorial problems admitting fast (polynomial time) algorithms and/or exact linear programming (LP) relaxations, e.g., shortest paths, optimum trees, and maximal matchings on various graphs (see Figure 6) with the exception of Steiner trees, which could be covered in other parts of the book. An authoritative and comprehensive source for the topics of this chapter is [1], while [21] is a more introductory and programming oriented source.