CMPE277 Syllabus -- Fall 06
Coursework:
- 35% Homeworks
- 30% Midterm exam
- 35% Final exam
Topics:
- Fundamentals
- Undirected Graphs
- Special graphs: Bipartite graphs, Complete Graphs, etc.
- Subgraphs
- Paths and Circuits
- Connectivity and Trees
- Directed Graphs
- Graph Search: DFS, BFS, Djikstra's Shortest Paths Algorithm
- Trees and Graph Matrices
- Enumeration of Spanning Trees
- Minimum Spanning Trees
- Steiner Trees
- Graph Matrices (The Google Matrix)
- DAGS (Directed Acyclic Graphs)
- Topological Sort
- Longest path problems
- Solving Constraint Networks
-
Network Flow and Matching
- Maximum Flow/ Min Cuts
- Menger's Theorems
- Circulations
- Minimum Cost Flow
- Multi-Commodity Flows
- Bipartite Matching
- Matchings
- Graph Partitioning
- K-L partitioning (FM variant)
- Spectral Graph Partitioning
- Multi-level Graph Partitioning
- Graph Isomorphism
- Graph Invariants
- Techniques for Graph and Subgraph Isomorphism
The CMPE277 Web:
Copyright 2006; Department of Computer Engineering,
University of California, Santa Cruz.
Portions of the CMPE277 Web may be reprinted or adapted for academic
nonprofit purposes, providing the source is accurately quoted and duly
credited.
Comments to:
martine@cse.ucsc
.edu
(Last Update:
11/09/06
)