2019/20 Taught Postgraduate Module Catalogue
COMP5940M Graph Theory: Structure and Algorithms
15 creditsClass Size: 40
Module manager: Professor Kristina Vuskovic
Taught: Semester 2 View Timetable
Year running 2019/20
Pre-requisite qualificationsCOMP3931 Graph Algorithms and Complexity Theory
MATH3033 Graph Theory
This module is not approved as an Elective
Module summaryGraph theory is a branch of mathematics that interfaces strongly with computer science. It developed enormously in recent decades due to its important applications in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, linguistics, chemistry, etc. Understanding structural properties of graphs is fundamental for the design of efficient algorithms. This module introduces students to main techniques and results from structural graph theory and considers their algorithmic applications. It covers classical results and more recent ones, and introduces current research techniques. This is a self-contained module; all necessary concepts and results used will be introduced and proved inside the module.
ObjectivesTo introduce students to some of the main techniques used to study the structure of graphs, and show how this leads to design of efficient algorithms.
On completion of this module, students should be able to:
- Prove classical results covered by the module;
- Understand the role of decompositions in graph-theoretic proofs and in algorithms on graphs;
- Be familiar with the decomposition by clique cut-sets and tree-decompositions ;
-Recognize how the methods learned can be extended and used to solve other problems.
On completion of the year/programme students should have provided evidence of being able to:
-to demonstrate in-depth, specialist knowledge and mastery of techniques relevant to the discipline and/or to demonstrate a sophisticated understanding of concepts, information and techniques at the forefront of the discipline;
-to exhibit mastery in the exercise of generic and subject-specific intellectual abilities;
-to demonstrate a comprehensive understanding of techniques applicable to their own research or advanced scholarship;
-proactively to formulate ideas and hypotheses and to develop, implement and execute plans by which to evaluate these;
-critically and creatively to evaluate current issues, research and advanced scholarship in the discipline.
Vertex colouring (greedy colouring heuristic, Brook’s Theorem, graphs with large chromatic numbers, Dizac’s Theorem, Hadwiger’s Conjecture)
Perfect Graphs (perfection of bipartite graphs, line graphs of bipartite graphs, perfect graph theorem.)
Chordal graphs (Lexicographic breadth-first search and recognition of chordal graphs, decomposition method and fast algorithms for colouring, clique and independent set problems)
Series parallel graphs
Tree decompositions (dynamic programming over tree decomposition).
|Delivery type||Number||Length hours||Student hours|
|Class tests, exams and assessment||1||2.00||2.00|
|Private study hours||116.00|
|Total Contact hours||34.00|
|Total hours (100hr per 10 credits)||150.00|
Private studyTaught session prep: 33 hours
Taught session follow-up: 33 hours
Self-directed study: 9 hours
Assessment activities: 40 hours
Opportunities for Formative FeedbackAttendance and formative coursework.
Methods of assessment
|Assessment type||Notes||% of formal assessment|
|Total percentage (Assessment Coursework)||40.00|
This module is re-assessed by exam only.
|Exam type||Exam duration||% of formal assessment|
|Standard exam (closed essays, MCQs etc)||2 hr 00 mins||60.00|
|Total percentage (Assessment Exams)||60.00|
This module is re-assessed by exam only.
Reading listThe reading list is available from the Library website
Last updated: 30/04/2019
Browse Other Catalogues
- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue
Errors, omissions, failed links etc should be notified to the Catalogue Team.SPT8