EPSRC logo

Details of Grant 

EPSRC Reference: EP/H021426/1
Title: Combinatorial Optimization Algorithms for Hereditary Graph Classes
Principal Investigator: Vuskovic, Professor K
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Sch of Computing
Organisation: University of Leeds
Scheme: Standard Research
Starts: 01 January 2010 Ends: 31 December 2012 Value (£): 96,293
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
20 Nov 2009 ICT Prioritisation Panel (Nov 09) Announced
Summary on Grant Application Form
Developing efficient algorithms for solving combinatorial problems has been of great importance to the modern technological society. The applications include diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc. Problems such as assigning frequencies to mobile telephones, can be modeled using graphs, and then the problem is reduced to coloring the vertices of the graph so that no two adjacent vertices receive the same color (of course the interest is in the minimum number of colors, and this is called the chromatic number of a graph). Many other applications in the real world reduce to the same coloring problem on graphs. Unfortunately, finding the chromatic number of a graph and some other optimization problems such as finding the size of a largest clique in a graph, are NP-complete in general. This means that it is highly unlikely that these problems can be solved efficiently on a computer (i.e. it is unlikely that polynomial time algorithms for these problems exist). One of the ways to deal with this situation is to find classes of graphs for which these problems can be solved in polynomial time.This project will focus on developing techniques for obtaining combinatorial optimization algorithms by expoliting structural analysis of hereditary graph classes. Many important graph classes are hereditary (i.e. closed under taking induced subgraphs), such as perfect graphs. For a difficult optimization problem, such as finding the chromatic number of a graph or the size of its largest clique, to be solvable in polynomial time for a given class, it means that this class must have some strong structure. The proposed research is about trying to understand what is this strong structure that will allow polynomial time combinatorial optimization algorithms, and developing techniques for obtaining the desired structure theorems and using them in algorithms.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.leeds.ac.uk