Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy

Prerequisites:  

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 sub graphs. Equivalence relations and classes in graphs. Parallel planarity testing. 

Topics