Materiale per il corso di Ottimizzazione Combinatoria
Material of the Combinatorial Optimization course

• 0 - Presentation of the course
  
• 1a - Linear programming
• 1b - Complexity
• 2a - Graphs
• 2a - Generating random graphs
  
• 2b - Graph search algorithms
• 2b - An example: the SSWPLD
  
• 3 - Minimum spanning tree
• 3b - Kruskal algorithm implementation
  
• 4 - Heaps
• 5 - Minimum spanning r-arborescence
• 6a - The shortest paths tree problem
  
• 6b - The s-t shortest path problem
• 6d - Advanced algorithms for the s-t SPP
• 6e - All pairs shortest paths
• 6f - Critical paths: CPM and PERT
• 7a - Maxflow (part I)
• 7b - Maxflow (part II)
• 7c - All pairs max flow
• 8 - Minimum mean cycle
• 9a - Min cost flow
• 9b - Network simplex algorithm
• 10 - The transportation problem
• 11 - Minimum cost bipartite matching
• 11b - Maximum cardinality matching
• 12 - Approximation algorithms
• 13 - Dynamic programming
  

• Ye, Han, Lin, "A note on the connection between the primal-dual and the A* algorithm".
• R. Gutman, "Reach-based routing: a new approach to shortest path algorithms optimized for road networks", 2004.
• P. Sanders, D. Schultes, "Highway Hierarchies Hasten Exact Shortest Path Queries", 2005.
• Goldberg, Kaplan, Werneck, "Reach for A*: efficient point-to-point shortest path algorithms", 2006
• G. Righini, "A new algorithm for the single-source Weber problem with limited distances", 2021.
  

2.10.2023