UAIC
Computer Science Department

Graph Algorithms

en ro

Olariu Emanuel Florentin

Autumn/Winter 2025-2026

Summary

The lectures will cover basic topics in Algorithmic Graph Theory. Accumulated knowledge will be applied in designing efficient algorithms for combinatorial optimization problems.

Administrative

Lectures: weekly in C309

Lecturers:  Olariu E. Florentin- C212, C building, phone: 0232 20 15 46, mail: fe.olariu@gmail.com;  Frasinaru A. Cristian - C212, C building

Office Hours: weekly, better by e-mail appointment

Grading:

  • Seminar activity (tests max. 20 points, participation to problem solving max. around 22 points): 0-42 points.
  • Homeworks: three exercise sheets, maximum 16 points each, 0-48 points. Each of the three homeworks can be solved by teams of at most 4 students; each student being leader/responsible for at least one problem from the set.
  • Written final test (compulsory): 0-70 points.
  • From a maximum of 90 points for seminar activity and homeworks the threshold for taking the written final test is of 30 points.
  • From a maximum of 160 points the threshold for promovating the course is of 80 points

Prerequisites: Knowledge of basic algorithm design and data structures.

Bibliography:

  • Cormen T. H., C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009
  • Croitoru C., Tehnici de baza in optimizarea combinatorie, Editura Univ. "Al. I. Cuza", Iasi, 1992.
  • Croitoru C., Introducere in proiectarea algoritmilor paraleli, Editura Matrix Rom, Bucuresti, 2002.
  • Diestel R., Graph Theory, electronic edition.
  • Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993
  • Tomescu I., Probleme de combinatorica si teoria grafurilor, Editura didactica si pedagogica, Bucuresti, 1981.

List of Topics:

  • Vocabulary of Graph Theory.
  • Path problems: graph traversal, shortest-paths, connectivity.
  • Minimum spanning trees: union-find, amortized complexity.
  • Matching theory.
  • Flows.
  • Polynomial time reductions between decision problems on graphs.
  • Approaching NP-difficult problems.
  • Planar graphs.
  • Tree decomposition.

 

Course information sheet.

Seminar scores. The bonus for LaTeX written homeworks will be added to the score of the 1st problem.

Final grades for the 23rd of January 2026 exam:

Final grades for the 12th of February 2026 exam:

Lectures: