Kristóf Bérczi:
Network flows and applications
Network flow theory provides a basic tool to treat conveniently various graph characterization and optimization problems, including the degree-constrained subgraph problem in a bipartite graph. Another general framework in graph optimization is matroid theory. For example, the problem of extending k given subtrees of a graph to k disjoint spanning trees can be solved with the help of matroids. A common generalization of these two big branches of combinatorial optimization is the theory of submodular flows, initiated by Edmonds and Giles. This covers not only the basic results on maximum flows and min-cost circulations from network flow theory and weighted matroid intersection from matroid theory, but also helps solving significantly more complex graph optimization problems. In this minicourse, we give an overview of the most fundamental results and techniques of this area.