=====  Graph Theory Applications =====

\\ 
|**Instructor**|\\
|**Rudiger Urbanke**|
|Office|[[http://plan.epfl.ch/?room=INR116|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
\\ 
\\ 
[[http://isa.epfl.ch/imoniteur_ISAP/!itffichecours.htm?ww_i_matiere=71646415&ww_x_anneeAcad=2012-2013&ww_i_section=946228&ww_i_niveau=6683117&ww_c_langue=en|Link]] to the official course description.  {{:en:courses:2012-2013:info.pdf|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 [[http://book.huihoo.com/pdf/graph-theory-With-applications/|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.
|Project |{{:en:courses:2012-2013:gta:project.pdf|Project.pdf}}|
==== Detailed Schedule ====

\\

^ Date    ^ Topic ^ Assignment  ^ Due Date/Solutions Posted ^ Remarks ^ 

|19Feb| Introduction; basic concepts, paths, cycles, special graphs, averaging principle  | | | |

|21Feb| Exercise Session 1 |{{:en:courses:2012-2013:gta:ex1.pdf|Ex1.pdf}}||

|26Feb| Eulerian graphs, Hamiltonian graphs |

|28Feb| Exercise Session 2 |{{:en:courses:2012-2013:gta:ex2.pdf|Ex2.pdf}}||

|05Mar| adjacency matrix A, powers of A, eigenvalues of A, incidence matrix B, rank of B |

|07Mar|Exercise Session 3 |{{:en:courses:2012-2013:gta:ex3.pdf|Ex3.pdf}}||

|12Mar| trees, cut edges, cut vertices, spanning trees, Cayley's formula, the connector problem, Kruskal's algorithm |

|14Mar|Exercise Session 4 |{{:en:courses:2012-2013:gta:ex4.pdf|Ex4.pdf}}||

|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 |{{:en:courses:2012-2013:gta:ex5.pdf|Ex5.pdf}}  |

|21Mar|Graded Homework 1 |{{:en:courses:2012-2013:gta:hw1.pdf|HW1.pdf}}| |

|26Mar|

|28Mar|

\\ 

|02Apr| Easter break - no course|
|04Apr| Easter break - no course|

|09Apr|

|11Apr| Midterm Exam ( INJ 218); 4:15pm-6pm | |{{:en:courses:2012-2013:gta:midterm_2013.pdf|Midterm.pdf}}||

|16Apr| Edge Colorings|

|18Apr| Exercise Session 6 |{{:en:courses:2012-2013:gta:ex6.pdf|Ex6.pdf}}||

|23Apr| Independent Sets and Ramsey Theory|

|25Apr|Exercise Session 7 |{{:en:courses:2012-2013:gta:ex7.pdf|Ex7.pdf}}||

|30Apr| Chromatic numbers|

|02May| Exercise Session 8 |{{:en:courses:2012-2013:gta:ex8.pdf|Ex8.pdf}}||

|07May|

|09May| Public holiday - no course|

|14May|Graded Homework 2 |{{:en:courses:2012-2013:gta:hw2.pdf|Hw2.pdf}}||


|16May|Network Flows, Max flow Min cut|

|21May|Feasible Flows|

|23May| Exercise Session 9 |{{:en:courses:2012-2013:gta:ex9a.pdf|Ex9.pdf}}||

|28May|

|30May|
==== Course Notes ====

\\ 

----