Course Contents (Syllabus):
Basic Graph Parameters. Directed Graphs, Cliques, Bipartite and Planar Graphs. Euler and Hamilton Cycles. Minimum Spanning Trees, Depth First Search, Breadth First Search, Shortest Paths. Maximum Flows. The Matching problem. NP-complete problems: Vertex Cover, Vertex Coloring, Maximum Clique.
Elective course, 4th year
Prerequisites and/or related courses:
Discrete Mathematics, Data Structures, Algorithms and Complexity.
Objectives:
- Modeling algorithmic problems in graphs
- Analyzing and proving graph properties
- Graph Algorithms
Teaching Methods:
Theory lectures (4h/week) and additionally seminars (2h/ 3 weeks) solving exercises.
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes
Recommended reading:
- Graph Theory and Algorithms, I. Manolopoulos, A. Papadopoulos, K. Tsichlas, Ekdosis Neon Technologion Mon. EPE, 2013 (in Greek).
- Introduction to Graphs, L. Kirousis, X. Mpouras, P. Spirakis, Y, Stamatiou, Ekdosis G. Dardanos - K. Dardanos O.E., 1999 (in Greek).
- Introduction to Algorithms vol. 1, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Panepistimiakes Ekdosis Kritis, 2009 (in Greek).
Bibliography:
- Graph Theory, A. Papaioannou, Notes, National Technical University of Athens, 2010 (in Greek).
- Graph Theory and Algorithms, I. Manolopoulos, A. Papadopoulos, K. Tsichlas, Ekdosis Neon Technologion Mon. EPE, 2013 (in Greek).
- Introduction to Graphs, L. Kirousis, X. Mpouras, P. Spirakis, Y, Stamatiou, Ekdosis G. Dardanos - K. Dardanos O.E., 1999 (in Greek).
- Introduction to Algorithms vol. 1, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Panepistimiakes Ekdosis Kritis, 2009 (in Greek).