2023/24 Taught Postgraduate Module Catalogue

COMP5940M Graph Theory: Structure and Algorithms

15 creditsClass Size: 40

Module manager: Dr Bogdan Alecu
Email: B.Alecu@leeds.ac.uk

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2023/24

Pre-requisite qualifications

COMP3931 Graph Algorithms and Complexity Theory
OR
MATH3033 Graph Theory
or equivalent

This module is not approved as an Elective

Module summary

Graph 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.

Objectives

To 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.

Learning outcomes
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.

Syllabus

Vertex colouring (greedy colouring heuristic, Brook’s Theorem, graphs with large chromatic numbers, Dirac’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).

Teaching methods

Delivery type	Number	Length hours	Student hours
Lectures	22	1.00	22.00
Tutorial	11	1.00	11.00
Private study hours			117.00
Total Contact hours			33.00
Total hours (100hr per 10 credits)			150.00

Opportunities for Formative Feedback

Attendance and formative coursework.

Methods of assessment

Coursework

Assessment type	Notes	% of formal assessment
Assignment	Coursework	10.00
Assignment	Coursework	10.00
Assignment	Coursework	10.00
Total percentage (Assessment Coursework)		30.00

This module is re-assessed by exam only.

Exams

Exam type	Exam duration	% of formal assessment
Standard exam (closed essays, MCQs etc)	2 hr 00 mins	70.00
Total percentage (Assessment Exams)		70.00

This module is re-assessed by exam only.

Reading list

The reading list is available from the Library website

Last updated: 26/09/2023

Disclaimer

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.PROD