SUBJECT
Title
Matroid theory
Type of instruction
lecture
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
Matroids and submodular functions. Matroid constructions. Rado's theorem, Edmonds’ matroid intersection theorem, matroid union. Algorithms for intersection and union. Applications in graph theory (disjoint trees, covering with trees, rooted edge-connectivity).
Readings
- András Frank: Connections in combinatorial optimization (electronic notes).
Further reading:
- W.J. Cook, W.H. Cunningham, W.R. Pulleybank, and A. Schrijver, Combinatorial Optimization, John Wiley and Sons, 1998.
- B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2000.,
- E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
- J. G. Oxley, Matroid Theory, Oxford Science Publication, 2004.,
- Recski A., Matriod theory and its applications, Springer (1989).,
- A. Schrijver, Combinatorial Optimization: Polyhedra and efficiency, Springer, 2003. Vol. 24 of the series Algorithms and Combinatorics.,
- D. J.A. Welsh, Matroid Theory, Academic Press, 1976.