Topics in Matroid Theory

Topics in Matroid Theory provides a brief introduction to matroid theory with an emphasis on algorithms. Matroid theory is at the heart of combinatorial optimization and has attracted various pioneers such as Edmonds, Tutte, Cunningham and Lawler among others. Matroid theory encompasses matrices, graphs and other combinatorial entities under a common, solid algebraic framework, thereby providing the analytical tools to answer related difficult algorithmic problems. The algorithmic approach for introducing matroid theory will make concepts of the theory accessible to graduate students and researchers from the combinatorial optimization, graph theory and algorithm communities. Algorithms in Matroid Theory contains a rigorous axiomatic definition of matroids along with other necessary concepts such as duality, minors, and representability as demonstrated in matrices, graphs and transversals. The author also presents a number of algorithms which resulted from the matroid theory and their extensions with substantial impact in the field of combinatorial optimization. Specifically, the matroid intersection and union algorithms of Edmonds, the recognition algorithm of graphic matroids by Tutte, and the recognition algorithm for totally unimodular matrices which results from the regular matroid decomposition theorem by Seymour.