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
- Special graphs
- Trees
- Cycles
- Grid graphs
- Planar graphs
- Chordal graphs
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)