**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.

*Contents:*

- Connectivity and traversability: Bounded connectivity, regularity, Overlay networks
- Graph coloring and graph NP-complete problems
- Topological graph theory: Imbeddings, genus and maps
- Analytic graph theory: Random graphs, Ramsey graphs and the probabilistic approach
- Graph measurements: Domination,and tolerance graph
- Small-world networks (on grid and uniform topology, Kleinberg's distribution)

*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:*

- Excerpts of the book by Shimon Even can be downloaded at http://www.wisdom.weizmann.ac.il/~oded/even-alg.html

View this course in the **RKBExplorer**

Back to MSc Curriculum.