Combinatorial Optimization and Graph Theory (ORCO - UGA)

Topic outline

• Slides of the course

  Collapse all Expand all

  Zoltan Szigeti
  

  • 

    Flows File
  • 

    Push-Relabel algorithm File
  • 

    Execution of Push-Relabel algorithm File
  • 

    Bipartite matching File
  • 

    Execution of the Hungarian method File
  • 

    General matching File
  • 

    Execution of Edmonds' algorithm File
  • 

    Matroids File
  • 

    Submodular functions File

• Other course notes

  Moritz Muhlenthaler

  • 

    Integer Polyhedra 1 File

    • polyhedra/polytopes and their vertices
    • TU matrices : definition and properties
    • TU matrices : applications

  • 

    Integer Polyhedra 1 : proofs File
  • 

    Integer Polyhedra 2 File

    • the (perfect) matching polytope
    • separation over the perfect matching polytope : min odd cuts
    • global minimum cuts

  • 

    Integer Polyhedra 2 : proofs File