Icpc-train-2014/graphs

Outlines

• Basic definitions
• Graph search
  • Properties of DFS and BFS
  • Topological ordering, DAG, strongly connected components
• Coloring
  • Vertex coloring
  • Edge 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
  • Blocking-flow algorithms
  • Bipartite matching
  • Unit networks
  • Other properties for bipartite matching
• Min-cost flows
  • Optimality criteria
  • Negative cycle cancellation algorithm
  • Cheapest augmentation algorithm

References

• Graph theory
  • Diestel Graph Theory (free to read online).
  • Lecture notes by Tero Harju
  • Bondy and Murty, Graph Theory with Applications
• Flows
  • Ahuja, Magnanti, Orlin Network flows (very old version)