Icpc-train-2014/graphs

Outlines

• Basic definitions
• Graph search
  • Properties of DFS and BFS
  • Topological ordering, DAG, strongly connected components
• Coloring
• Euler tour
• MST
  • Red/blue rules
• Shortest paths
  • Optimality criteria
  • Dijkstra's algorithm
  • Graphs with negative weights: Bellman-Ford algorithm, Johnson's algorithm
  • Finding negative cycles
• Maximum flows
  • Ford-Fulkerson algorithm
  • Flow decomposition
  • Weakly-poly time: largest augmentation
  • Strongly-poly time algorithm: Edmond-Karp
  • Bipartite matching
  • Blocking-flow algorithms.
  • Unit network
• Min-cost flows