Advanced Graph Theory (3 ECTS)

The purpose of this advanced course is to present the aspects of graph theory beneficial for the design of resilient systems. "Advanced" means here that the basics of graph theory (such as paths, traversals, trees, maximum flow, planarity, basic graph NP-complete problems, etc.) are already known. So, "advanced" is here the "discovery" of concepts that have been recently (or not) introduced in computer science to model problems related to computability, efficiency, or fault-tolerance).

Graph theory has long become recognized as one of the more useful mathematical subjects for the computer science student to master. The approach which is natural in computer science is the algorithmic one; the interest is not so much in existence proofs or enumeration techniques, as it is in finding efficient algorithms for solving relevant problems, or alternatively showing evidence that no such algorithms exist.


Suggested readings:

S. Even: Graph Algorithms, Computer Science Press, 1979, 249 pp.

J.L. Gross and J. Yellen (Eds.): Handbook of graph theory, CRC Press, 2003, 1192 pp.

Courseware examples and locations where taught:

Line of teaching

View this course in the RKBExplorer

Back to MSc Curriculum.