Advanced and algorithmic graph theory
3 Lecture/1 Practical
(MAT.464 / MAT.465)

E. Dragoti-Çela
Department of Discrete Mathematics

• Time and Place
  Lecture :
  Mondays, 10:15-12:00, SR AE06, Steyrergasse 30, ground floor
  Fridays, 08:15-10:00, SR AE06, Steyrergasse 30, ground floor (every second week)
  
  Practical:
  Fridays., 08:15-10:00, SR AE06, Steyrergasse 30, ground floor (every second week)

• Start: Monday, February 29, 2016, 10:15-12:00, SR AE06, Steyrergasse 30, ground floor
• Registration
via TUGonline until March 19, 2016
• Contents and prerequisites

This course deals with concepts from graph theory such as connectivity, trees and decompositions, Hamiltonian cycles, planar graphs, graph coloring, perfect graphs, covering problems and random graphs. Most of the topics will be discussed both from a theoretical and from an algorithmical point of view. Hence also a number of topics from the field of algorithmic graph theory and optimization problems in graphs will be considered.


Chapters:

• Connectivity, trees and decompositions
• Hamiltonian cycles
• Planar graphs and plane duality
• Colouring problems
• Perfect graphs
• Covering problems
• Random graphs and randomized algorithms
• Literature

The main sources of literature


• Bella Bollobas, Modern Graph Theory (Graduate Texts in Mathematics), corrected and extended edition, Springer, 2013.
• G. Chartrand, L. Lesniak, P. Zhang, Graphs & Digraphs (Textbooks in Mathematics), Taylor & Francis Inc, 6th revised edition, 2015.
• R. Diestel, Graph Theory (Graduate Texts in Mathematics), fourth edition, Springer, 2010
• M.Ch.Golumbic, Algorithmic graph theory and perfect graphs, second edition, Elsevier Ltd, 2004
• Assessment

The practical assessment will be permanent and based on a score of points collected as follows


• by solving exercise examples independently; at most 3 points;
  At the beginning of every practical class the participants have to declare which exercise examples they have solved and prepared for presentation.
  At the end of the course they will be credited with the percentage of the exercise examples they have declared to have solved during the course multiplied by three
• by presenting the solution of exercise examples in the class;
  The presentatation of an exercise example in the class will be credited with at most 4 points corresponding to the correctness and completeness of the solution as well as the quality of the presentation.
• by participating at a written exam at the end of the course; at most 15 points.


The written exam: There will be exactly two possibilities to take the writen exam; one at the end of the course and another one at the beginning of the next summer term. After an unsuccessful try at the end of the winter term students can have a second try at the beginning of the next summer term. In this case only the points collected during the second try will count.


The writen exam will take place on June 30, 8:15-10:00, in SR AE06 (TUGonline-Name STEG050);
the registration for the exam has to be done via TUGonline.


The overall score is computed as follows


P= 3 * ((k)/(k_a)) + 12*(t) + 15 (p),


where


k     number of exercise examples prepared all along the course,


k_a   overall number of exercise examples which have been available during the course,


t     overall sum of points obtained by presenting exercise examples in the class (scaled between 0 and 1)


p     score of the written exam (scaled between 0 und 1),




Grade obtained for the practical according to the overall score:


5    0 <= P < 15
4    15 <= P <= 18
3    18 < P <= 22
2    22 < P <=26
1    26< P

The lecture will be assessed by an oral examination.
The dates for the oral exams will be specified in agreements with the students.


There will be up to 3 Dates per term if needed;
they will be announced in TUGonline on time;


The registration for the oral examination should be done via TUGonline.


• Work sheets (pdf)

  1st work sheet (pdf), to be discussed on March 14

  2nd work sheet (pdf), to be discussed on April 14

  3d work sheet (pdf), to be discussed on April 28

  4th work sheet (pdf), to be discussed on Mai 23

  5th work sheet (pdf), to be discussed on June 9 and June 16

  6th work sheet (pdf), to be discussed on June 23

Back to my homepage

Last update: June 2016