Fragments of Structural and Algorithmic Graph Theory
Lectures
Time | Room | Lecturer | Date |
---|---|---|---|
Tue 16-18 | B222 | Martin Milanic | 01.09.2015-04.09.2015 |
Wed 16-18 | B222 | Martin Milanic | 01.09.2015-04.09.2015 |
Thu 16-18 | B222 | Martin Milanic | 01.09.2015-04.09.2015 |
Fri 14-16 | B222 | Martin Milanic | 01.09.2015-04.09.2015 |
General
This is a self-contained mini-course on graph theory, given by Prof. Martin Milanič, from the University of Primorska, in Koper, Slovenia. Prof. Milanič is visiting the Department of Computer Science in the week 31 August - 4 September, with an Erasmus Exchange for Teachers. The course can give up to 3 credits (see below Completing the course)
Graph theory is a relatively young branch of discrete mathematics that has been developing rapidly in the last decades, mostly due to its many applications in the modern world in fields as diverse as computer science, social sciences, biology and logistics. With (finite) graphs, one can model pairwise relations between entities such as computers, individuals, proteins in a cell and cities. In their mathematical abstraction, entities are usually referred to as vertices, and the fact that that two entities are related is represented by connecting two vertices by an edge.
- Review of basic notions in graph theory, algorithms and complexity. Basic graph theoretic definitions. Graph represenatations. Classes P and NP, NP-hardness, polynomial reductions, 2-SAT problem, 3-SAT problem.
- Graph traversal algorithms and their applications. Breadth-first search. Application: A polynomial time algorithm for 2-SAT. Depth-first search. Application: topological sorting. Applications of 2-SAT to graph theory problems. Application of topological sorting: shortest paths in directed acyclic graphs.
- Graph colorings. Chromatic number, upper and lower bounds. Greedy algorithm and its analysis. The Four Color Theorem. Hadwiger's Conjecture. Brooks' Theorem. Edge colorings and Vizing's Theorem. List colorings. Galvin's Theorem. Algorithmic aspects of graph coloring. NP-completeness of the problem of computing the chromatic number. Applications in scheduling.
- Perfect graphs and their subclasses. Basic theory and examples of hereditary graph classes. Perfect graphs and their properties. Cographs. Split graphs and threshold graphs. Chordal graphs. Interval graphs. Efficient algorithms for various problems based on structural properties of graphs in these classes.
Completing the course
Attending all four lectures gives 1 credit. Solving the exercises handed out during the course gives at most 2 extra credits as follows.
Literature and material
Course materials
- Glossary of basic definitions
- 1.9.2015 First lecture. The slides have been sent by e-mail. Here are the exercises for the first lecture.
- 2.9.2015 Second Lecture. The slides have been sent by e-mail. Here are the exercises for the second lecture.
- 3.9.2015 Third Lecture. Slides have been sent by e-mail. Extra slides have been sent by e-mail. Here are the exercises for the third lecture.
- 4.9.2015 Fourth lecture. Slides have been sent by e-mail. Here are the exercises for the fourth lecture.
References
The course is based on several sources (books and research articles). The following is a list of some relevant literature:
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, second edition. McGraw-Hill, 2001.
- M. R. Garey, D. S. Johnson, Computers and Intractability: A guide to the theory of NP-Completeness, 1979.
- M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, Volume 57 in the series Annals of Discrete Mathematics. North Holland, second edition, 2004.
- A. Brandstädt, V. B. Le, J. P. Spinrad. Graph Classes: A Survey. SIAM, 1999.
- V. V. Vazirani. Approximation Algorithms, Springer-Verlag, 2001.
- J. A. Bondy, U. S. R. Murty. Graph Theory, North-Holland, Springer-Verlag, 2008.
- B. Korte, J. Vygen. Combinatorial Optimization. Theory and Algorithms, Volume 21 in the series Algorithms and Combinatorics, Springer-Verlag, druga izdaja, 2002.
- R. Diestel, Graph Theory. Springer, 2006.
- A. Schrijver, Combinatorial Optimization, Springer, 2003.