Coursework:

• 35% Homeworks
• 30% Midterm exam
• 35% Final exam

Topics:

• Fundamentals
  
  1. Undirected Graphs
  2. Special graphs: Bipartite graphs, Complete Graphs, etc.
  3. Subgraphs
  4. Paths and Circuits
  5. Connectivity and Trees
  6. Directed Graphs
  7. Graph Search: DFS, BFS, Djikstra's Shortest Paths Algorithm
• Trees and Graph Matrices
  
  1. Enumeration of Spanning Trees
  2. Minimum Spanning Trees
  3. Steiner Trees
  4. Graph Matrices (The Google Matrix)
• DAGS (Directed Acyclic Graphs)
  
  1. Topological Sort
  2. Longest path problems
  3. Solving Constraint Networks
• Network Flow and Matching
  
  1. Maximum Flow/ Min Cuts
  2. Menger's Theorems
  3. Circulations
  4. Minimum Cost Flow
  5. Multi-Commodity Flows
  6. Bipartite Matching
  7. Matchings
• Graph Partitioning
  
  1. K-L partitioning (FM variant)
  2. Spectral Graph Partitioning
  3. Multi-level Graph Partitioning
• Graph Isomorphism
  
  1. Graph Invariants
  2. Techniques for Graph and Subgraph Isomorphism

Portions of the CMPE277 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited.