CS 743: Advanced Graph Algorithms

Course Contents:

Review of important sequential graph algorithms.

 

Introduction to parallel models for computation. General techniques for fast parallel computations on vectors and lists and their applications to design of efficient parallel graph algorithms.

 

Parallel dynamic programming and its applications to expression graphs.

 

State-of-art algorithms for depth first search of directed and undirected graphs. NC-algorithms for st-numbering and open ear decomposition.

 

Parallel algorithms for graph optimization problems. Algorithms for graph coloring. Decomposition of graph into simpler subgraphs. Equivalence relations and classes in graphs. Parallel planarity testing.

 

Books and References

1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman.Design and Analysis of Computer Algorithms, Addison Wesley, 1974.
2. S. Even.Graph Algorithms, Computer Science Press, 1979.
3. A. Gibbons and W. Rytter.Efficient Parallel Algorithms, Cambridge University Press, 1988.
4. M. J. Quinn.Designing Efficient Algorithms for Parallel Computers, McGraw Hill, 1987.
5. H. Sparkias and A. Gibbon (Editors).Lecture notes on Parallel Computation, Cambridge University Press, 1993.
6. Research papers.