| EPSRC Reference: |
EP/E034985/1 |
| Title: |
Parameterized Problems on Directed Graphs |
| Principal Investigator: |
Gutin, Professor G |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
Standard Research |
| Starts: |
19 September 2007 |
Ends: |
18 September 2010 |
Value (£): |
344,495
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic & Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
It is well-known that the vast majority of computational problemsare intractable, i.e., we do not have efficient algorithms solvingevery instance of such a problem. One way to cope with intractable problems is to is to parameterize them by introducing asuitable positive integer parameter that assumes only small tomoderate values for instances of our interest. In this case, theintractable problem under consideration can often be solved by efficientparameterized algorithms (i.e., algorithms that are polynomial if we consider the parameter as a constant, and the exponentin the polynomial does not depend on the parameter). The area of theoretical computer science studying the above approach is called fixed-parameter algorithmics(FPA). FPA has several applications in biology and social sciences.It is well-known that directed graphs are at least as important incomputer science and its applications as their undirectedcounterparts. Nevertheless, almost all results on graph algorithmsin FPA have been on undirected graphs. There are several reasons forthat including the fact that usually parameterized problems ondirected graphs are much harder to investigate than problems ontheir undirected counterparts.We will study FPA for directed graphs. In particular, we willinvestigate algorithmic extremal structure of digraphs, andthe possibility to apply recently developed methods on undirected graphFPA to directed graphs. We will also develop new FPA methods anddesign parameterized exact algorithms and parameterized approximation algorithms for special classes of directed graphs.
|
|
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: |
|