Course description:

Topics covered:

• Exploring a graph: breadth-first search (BFS), depth-first search (DFS), and their applications
• Shortest path algorithms in digraphs (Dijkstra, Bellman-Ford)
• Minimum length spanning trees - the greedy algorithm
• Minimum cost arborescence algorithm
• Eulerian graphs and digraphs, orientations of graphs and mixed graphs
• Matchings in bipartite graphs - theorems of K?onig and Hall
• Maximum cardinality and maximum weight matching algorithms in bipartite graphs
• Edge colorings, timetables, another theorem of K?onig
• Menger's theorem, Network flows, Max-flow Min-cut theorem
• Flow algorithms by Ford and Fulkerson, and by Edmonds and Karp; Minimum cost flows
• The assignment problem and the transportation problem
• Circulations, Hoffman's theorem
• Matchings in general graphs - Tutte's theorem, the Tutte-Berge formula
• Maximum cardinality matching algorithm in general graphs
• Computing the edge-connectivity of graphs
• Flow- and Cut-equivalent trees
• Chordal graphs, maximum weight stable sets in chordal graphs
• Approximation algorithms - the traveling salesman problem, the Steiner tree problem
• Minimum multiway cut, minimum k-cut, multicut in trees
• Facility location problems
• Basics of Linear Programming
• Dynamic Programming techniques
• Scheduling problems on parallel machines