Materiale per il corso di Ottimizzazione su Grafo

• 1a - Linear programming
• 1b - Graphs
• 1c - Complexity
• 2a - Generating random graphs
  
• 2b - Graph search algorithms
• 2c - Critical path
  
• 3 - Minimum cost bipartite matching
• 4 - Minimum spanning tree
• 5 - Kruskal algorithm implementation
• 6a - Heaps
• 6b - UnionFind
• 7 - Minimum spanning tree re-optimization
  
• 8 - Minimum spanning r-arborescence
• 9 - Shortest paths arborescence
• 10 - s-t shortest path
• 11 - Landmarks
• 12 - Reach
• 13 - Highway hierarchies
• 14 - Maxflow (part I)
• 15 - Maxflow (part II)
• 16a - All pairs max flows
• 16b - All pairs shortest paths
• 17a - Minimum mean cycle
• 17b - Min cost flow (part I)
  
• 18 - Min cost flow (part II)

• 19 - Network simplex algorithm
• 20 - Max cardinality matching
  
• 21a - Min cost transportation
• 21b - Chinese postman
• 21c - Paths and matchings in automated warehouses
• 22 - Approximation algorithms on graphs

• Dynamic programming
  

• Gabow Galil Spencer Tarjan (1986)
  

• Bertsekas, Auction algorithm 1990
• Goldberg Kennedy, Cost scaling, 1995
• Golberg Kennedy, Dual updates, 1996
• Della Croce et al., Shortlists, 2025
  

• Righini, Righini, Skewed Kruskal algorithm, 2022
• Lecchi Righini, Skewed Kruskal algorithm, 2025
• Righini, Ri-ottimizzazione minimo spanning tree 2021
  

• Zwick, Implementation of Edmonds algorithm, 2013
  

• 2013 Vasiljevic Danilovic - linear time algo for SPP

• Ye, Han, Lin, "A note on the connection between the primal-dual and the A* algorithm".
• Ikeda et al - Consistent Astar, 1994
• 2021 Ahmadi et al - Bi-obj search Bidirectional Astar
  

• 2005 Goldberg Werneck - ALT algorithm
• 2005 SODA Goldberg Harrelson - ALT algorithm
• Goldberg Werneck - Landmarks selection (slides)
• 2011 Tretyakov et al - Landmark-based SPP
  

• R. Gutman, "Reach-based routing: a new approach to shortest path algorithms optimized for road networks", 2004.
• Goldberg, Kaplan, Werneck, "Reach for A*: efficient point-to-point shortest path algorithms", 2006

• P. Sanders, D. Schultes, "Highway Hierarchies Hasten Exact Shortest Path Queries", 2005.
• 2007 Sanders Schultes - Engineering fast route planning algorithms

• Barbato Ceselli Righini, "Paths and matchings in automated warehouses", 2019
  

13.11.2025