PhD Scholarship: Structure of hereditary graph classes and its algorithmic consequences

University of Leeds - Computing

Name of School Contact: Kristina Vušković
Contact Details: Email:
                                Tel: +44(0)113 343 5443
School website:
How to apply: 
Degree Level: Research Postgraduate  
Scholarship Type: International, Home/EU                     
Number available: 1
Funding Type: School of Computing

Applicants should read the information below for further details on the scholarship or visit the School web site given below.

Further Information:

Developing efficient algorithms for solving combinatorial optimization problems is of great importance to the modern technological society. Many diverse applications in the real world when modelled by graphs reduce to classical optimization problems such as optimally coloring the vertices of a graph (the chromatic number), or finding the size of a largest clique or a stable set. These problems are unfortunately NP-hard in general, but become polynomially solvable when restricted to different classes of graphs.

This project will focus on developing techniques for obtaining combinatorial optimization algorithms by exploiting structural properties of hereditary graph classes (i.e. classes closed under taking induced subgraphs). For a difficult optimization problem to be solved in polynomial time for a given class, it means that this class must have some strong structure. This research is about understanding structural reasons that enable the design of efficient algorithms, and developing techniques for obtaining the desired structure theorems and using them in algorithms.

Financial Information:

This award will cover the cost of academic fees and provide a maintenance allowance of at least £14,296 per year for a maximum for 3 years, subject to satisfactory progress.  

Minimum Academic Requirements (if English is not your first language, then candidates must also meet the University’s English language requirements):

Applications are invited from candidates who have achieved or expecting a minimum of a UK upper second class (hons) degree or equivalent, in a field relevant to the project.

If you first language is not English, you will need to satisfy the University of Leeds English language requirements:  

Any Additional Requirements:

Please be aware, this project is linked to, but not funded by the following EPSRC project:

Share this PhD
  Share by Email   Print this job   More sharing options
We value your feedback on the quality of our adverts. If you have a comment to make about the overall quality of this advert, or its categorisation then please send us your feedback
Advert information

Type / Role:



Northern England