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:
    1. Introduction graph algorithms
    2. Spanning-trees, branching and connectivaty
    3. Network-flows
    4. Matchings
    5. Planar graphs
    6. Eulerian and Hamiltonian Tours
    7. 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.