Graph Algorithms (in English)

• 39 hrs lectures
• 13 hrs projects

• 60 pts final exam (written part)
• 15 pts mid-term test (written part)
• 25 pts projects

Introduction to graph theory with focus on graph representations, graph algorithms and their complexities.
Fundamental ability to construct an algorithm for a graph problem and to analyze its time and space complexity.

Foundations in discrete mathematics and algorithmic thinking.

• Electronic copy of lectures.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition. MIT Press, 2009.
• J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
• K. Erciyes: Guide to Graph Algorithms (Sequential, Parallel and Distributed). Springer, 2018.

• A. Mitina: Applied Combinatorics with Graph Theory. NEIU, 2019.

1. Introduction, algorithmic complexity, basic notions and graph representations.
2. Graph searching, depth-first search, breadth-first search.
3. Topological sort, acyclic graphs.
4. Graph components, strongly connected components, examples.
5. Trees, minimal spanning trees, algorithms of Jarník and Borůvka.
6. Growing a minimal spanning tree, algorithms of Kruskal and Prim.
7. Single-source shortest paths, Bellman-Ford algorithm, shortest path in DAGs.
8. Dijkstra algorithm. All-pairs shortest paths.
9. Shortest paths and matrix multiplication, Floyd-Warshall algorithm.
10. Flows and cuts in networks, maximal flow, minimal cut, Ford-Fulkerson algorithm.
11. Matching in bipartite graphs, maximal matching.
12. Graph coloring.
13. Eulerian graphs and tours, Hamiltonian graphs and cycles.

1. Solving of selected graph problems and presentation of solutions (principle, complexity, implementation, optimization).

• Mid-term exam - 15 points.
• Projects - 25 points.
• Final exam - 60 points. The minimal number of points which can be obtained from the final exam is 25. Otherwise, no points from the final exam will be assigned to a student.