PhD Scholarship: Structure of hereditary graph classes and its algorithmic consequences
University of Leeds - Computing
|Funding for:||UK Students, EU Students, International Students|
|Funding amount:||Maintenance: £14,296|
|Placed on:||1st December 2016|
|Closes:||6th January 2017|
Name of School Contact: Kristina Vušković
Contact Details: Email: K.Vuskovic@leeds.ac.uk
Tel: +44(0)113 343 5443
School website: https://engineering.leeds.ac.uk/info/20132/school_of_computing
How to apply: http://www.leeds.ac.uk/info/130206/applying/91/applying_for_research_degrees
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.
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.
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: http://www.leeds.ac.uk/projectleeds/info/123100/admissions/143/entry_requirements
Any Additional Requirements:
Please be aware, this project is linked to, but not funded by the following EPSRC project: http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/N019660/1
Share this PhD
Type / Role: