CMPSC 292A Algorithmic Graph Theory

Graphs are a remarkably versatile combinatorial object, used to model social, neural, road and computer networks, execution flow of programs, relations in databases, and countless other things. In this class we will investigate computational problems whose inputs are graphs, and how algorithms for such problems can exploit the structure of the input graph to improve performance. The focus will be on provable worst-case running time performance of our algorithms. On the way the class will expose students to some of the modern structural graph theory.

Prereqisites: CS130B or equivalent. Proficiency in understanding and writing mathematical proofs.