MA4208: Optimization/Graph Algorithms
Text
W. Kocay and D.L. Kreher , Graphs, Algorithms, and Optimizationi , Chapman \&
Hall/CRC Press , Boca Raton, Florida, 2005.
Description
An introduction to linear and integer programming and related Graph
problems. Topics include simplex algorithm, duality, Branch-and-Bound
and Branch-and-Cut, shortest paths, spanning trees, matchings, network
flow, graph coloring and perfect graphs.
Prerequisites: MA3210
Syllabus
We will discuss the following topics:
-
Introduction graph algorithms
-
Spanning-trees, branching and connectivaty
-
Network-flows
-
Matchings
-
Planar graphs
-
Eulerian and Hamiltonian Tours
-
Linear programing
Grading
Your grade will be based on several written assignments and
a final examination. Assignments may or may not include
programs and proof, depending on students background.
Start every written assignment at the top of a
new page, put your name at the beginning of each page and do not stable
different problems together. I expect the problems to be well written
in full English sentences with no gaps in detail or logic. Please
be as elegant and as concise as possible. Cite all references.
The software
MA4208src
will be used for Homework 2 and Homework 3.
The software
pivot
will be used as an aide to learning the simplex algorithm.