Graph Theory Applications
| Instructor | |
| Rudiger Urbanke | |
| Office | INR 116 |
| Phone | +4121 6937692 |
| Email | rudiger.urbanke@epfl.ch |
| Office Hours | By appointment |
| Teaching Assistants | |
| Lazlo Czap (for first 3 weeks) | |
| Phone | +4121 6937516 |
| Office | BC 048 |
| Email | laszlo.czap@epfl.ch |
| Office Hours | Office Hours TBD |
| Siddhartha Brahma | |
| Phone | +4121 6936654 |
| Office | INR032 |
| Email | siddhartha.brahma@epfl.ch |
| Office Hours | Office Hours TBD |
| Stanko Novakovic | |
| Phone | +4121 6937543 |
| Office | INN318 |
| Email | stanko.novakovic@epfl.ch |
| Office Hours | Office Hours TBD |
| Student Assistant | |
| Yannik Messerli | |
| Email | yannik.messerli@epfl.ch |
| Lectures: | | Tuesday | 11:15 - 13:00 | Room: INM203 |
| | | Thursday | 16:15 - 18:00 | Room: INM 201 |
Language: English Coefficient/Crédits: 4 ECTS
Link to the official course description. CourseInformation.pdf
Course Description
This class focuses on graph theory problems arising in Computer Science and Communications and discusses how to use methods and results from graph theory to solve them. The class will cover topics such as:
Introduction to basic concepts in graph theory
Job scheduling and graph coloring
Network routing and graph connectivity
Labyrinths and Eulerian paths
Archeological data and trees
VLSI design and planar graphs
Internet routers and bipartite graphs
Wireless Networks and geometric graphs
Grade
The grade will have four components - Homeworks (10%), Project (20%), Midterm Exam (30%) and Final Exam (40%)
Tentatively, there will be two homework sets on both sides of the Midterm exam.
The precise topic of the project will be discussed in the class during the semester.
Textbook
We will be using the book Graph Theory with Applications by J.A. Bondy and U.S.R. Murty. You may find the electronic version of the book here
Special Announcements
For the Final Exam, just like the midterm, you are allowed to bring one A4 sheet with all the information you can write into it! Best of Luck!
Project
Please announce your group by April 25th.
The due date of the project is Thursday May 30th.
Detailed Schedule
| Date | Topic | Assignment | Due Date/Solutions Posted | Remarks |
| 19Feb | Introduction; basic concepts, paths, cycles, special graphs, averaging principle | | | |
| 26Feb | Eulerian graphs, Hamiltonian graphs |
| 05Mar | adjacency matrix A, powers of A, eigenvalues of A, incidence matrix B, rank of B |
| 12Mar | trees, cut edges, cut vertices, spanning trees, Cayley's formula, the connector problem, Kruskal's algorithm |
| 19Mar | proof of Kruskal's algorithm; matchings and vertex covers; there will be only one hour of lecture and one hour of exercise session |
| Exercise Session 5 | Ex5.pdf |
| 02Apr | Easter break - no course |
| 04Apr | Easter break - no course |
| 23Apr | Independent Sets and Ramsey Theory |
| 09May | Public holiday - no course |
| 16May | Network Flows, Max flow Min cut |
Course Notes