Icpc-train-2014/graphs

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 15:03, 2 พฤศจิกายน 2557 โดย Jittat (คุย | มีส่วนร่วม) (→‎Outlines)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

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