Course of Combinatorial Optimization and Graph Theory, ORCO

Slides :

  • Flows (pdf)

  • Push-Relabel Algorithm (pdf), Execution of the Push-Relabel Algorithm (pdf)

  • Matchings in bipartite graphs (pdf), Execution of the Hungarian Method (pdf)

  • Matchings in general graphs (pdf), Execution of Edmonds' Algorithm (pdf)

  • Matroids (pdf)

  • Applications of submodular functions (pdf)

    Papers to be presented in this order:

  • 1. Strong orientation of a connected graph for a crossing family (pdf)

  • 2. On packing arborescences in temporal networks (pdf)

  • 3. A generalization of Petersen's theorem (pdf)

  • 4. Minimum bounded degree spanning trees (pdf)

  • 5. On disjoint trees and arborescences (pdf)

  • 6. A note on disjoint arborescences (pdf)

  • 7. A linear time algorithm to find a pair of arc-disjoint spanning in-arborescences and out-arborescences in a directed acyclic graph (pdf)

  • 8. A simple algorithm and min-max formula for the inverse arborescence problem (pdf)

  • 9. Reconfiguration of the union of arborescences (pdf)

  • 10. A short proof of the tree-packing theorem (pdf)

  • 11. Note on the path-matching formula (pdf)

  • 12. Matching-covered graphs (pdf)

  • 13. Conservative weightings and ear-decompositions of graphs (pdf)

  • 14. An algorithm for minimum cost arc-connectivity orientation (pdf)

  • 15. On a theorem of Mader (pdf)

  • 16. Minimizing submodular functionsover familier of sets (pdf)

  • 17. Layers and matroids for the travelling salesman's path (pdf)