Icpc-train-2014/graphs

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

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