SOME PRIMAL-DUAL THEOREMS IN GRAPH THEORY - A STUDY
Venkata Harish Immadi · 2012
The objective of this report is to present some central min-max theorems in graph theory from the view point of linear programming. In the introductory chapter, we review the well known Max-flow Min-cut theorem and discuss the standard proof using Ford-Fulkerson algorithm. The next chapter will discuss some graph theoretic consequences of the Max-flow Min-cut theorem in combinatorial optimization. In the third chapter we present the proof of the Max-flow Min-cut theorem and Konig’s theorem using the properties of total unimodular matrices in linear programming. In the fourth chapter, we discuss the problem of Concurrent Multi-commodity Flow(CMFP) and present a linear programming formulation.