|
| EPSRC Reference: |
EP/D040191/1 |
| Title: |
clique-width |
| Principal Investigator: |
Dr H Muller |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research |
| Starts: |
01 February 2007 |
Ends: |
31 July 2010 |
Value (£): |
98,147
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic and Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
09 Nov 2005
|
Computer Science (Tech) November 2005
|
Announced
|
|
|
Summary |
Graphs are used as models in various applications ranging from supply
networks to interaction between human beings. These applications
require algorithms processing graphs. Usually the input of an
algorithm is given as a list of vertices (branching points of the
network, persons, or objects) and a list of edges (connections or
relations between vertices). Lots of practically important or
theoretically interesting problems on graphs are intractable if the
graph is given this way, but become tractable if instead a
construction manual is provided. Such a manual describes basic
building blocks and simple operations to combine components.
The parameter clique-width measures the complexity of such a
construction manual in the following way. Our basic block is a graph
consisting of one vertex and no edges. The vertex has a colour. The
operations are disjoint union (set one graph aside another one without
creating any new edges), recolouring of vertices (for example: all
blue vertices become green), and inserting edges (for example: connect
each red vertex to each yellow one). The complexity is the number of
different colours used. A construction plan involving k colours is
called k-expression. For each graph G, the minimum k such that a
k-expression for G exists is called cwd(G).
Finding a cwd(G)-expression for a given graph G is itself an
algorithmic problem. Unfortunately very little is known about it:
* We know the graphs that are constructible using only one colour.
These are the graphs without edges.
* Two colours suffice if and only if
the graph does not contain a path on 4 vertices.
* There is an efficient algorithm deciding whether one can
construct a graph using at most 3 colours.
This project will extend this knowledge. We consider graphs in special
classes. These classes are restricted to enforce an easy structure of
the graphs within, but are rich enough to allow graphs of arbitrary
clique-width. Our goal is an efficient algorithm computing a
cwd(G)-expression for each graph G in the special class.
It is not known whether such an algorithm exists. In case we cannot
design an efficient algorithm we will provide some evidence that the
desired algorithm does not exist.
|
| Final Report Summary |
|
No final report summary is available for this grant.
|
| Further Information: |
|
| Organisation Website: |
http://www.leeds.ac.uk |
|
|