DM201: Graph algorithms with practical applications (10 ECTS)

STADS: 15003201

Level
PhD course

Teaching period
The course is offered in the spring semester.
Offered according to needs.

Teacher responsible
No responsible teachers found, contact the department if necessary

Timetable
There is no timetable available for the chosen semester.

Comment:
AFLYST F2009!

Prerequisites:
None

Academic preconditions:
The Bachelor degree must be passed. The contents DM507 and DM508 must be known.

Course introduction
The purpose of the course is to give an introduction to the essential aspects of algorithms on graphs. Several of the methods treated in the course are of great practical use within areas such as transportation, network design, scheduling, assignment of jobs to workers/machines. The connections to such applications will be treated carefully in the course.

Expected learning outcome
After taking the course the student is expected to be able to:

• apply the algorithms from the course to concrete problem instances
• explain the algorithms from the course and prove their complexity
• apply the theory of flows to prove structural results for graphs
• explain the results on matroids treated in the course and show how to use these results on graph problems
• explain algorithms for maximum (weighted) matching and show how to use these results in job assignment problems
• explain the results on graph connectivity treated in the course
• explain the results on graph orientations treated in the course
• explain algorithms for routing problems, in particular the traveling salesman problem
• explain the results on graph colourings and heuristics for colouring treated in the course and also applications of graph colouring to scheduling problems
• explain the practical applications of graph algorithms treated in the course
• explain the colour-coding method and how one uses the method to find “long” paths and cycles in a graph in polynomial time
• apply the algorithms and algorithmic ideas from the course to new problems which resemble problems from the course

Subject overview
Flows in networks, assignment and transportation problems, the primal-dual algorithm, matchings, connectivity in graphs, paths and cycles, the traveling salesman problem, orientations of graphs, greedy algorithms and matroid algorithms, disjoint paths and trees, minimum cost branchings, polynomial algorithms for finding path and cycles of guaranteed minimum length.

Literature
There isn't any litterature for the course at the moment.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
(a) Project reports, passed/not passed and internal evaluation by lecturer. The examiner will have access to the reports during the oral examination. The projects may involve programming assignments.
(b) After the 4th quarter there will be a 30 minutes oral exam with 30 minutes for preparation. All aids allowed. At the exam there may be questions in the topics of the projects. Danish 7 mark scale, external examiner.
(c) Reexamination after 2nd quarter.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 2 timer om ugen
Eksaminatorietimer: 2 timer om ugen
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.