Graphs, Algorithms and a tiny bit of Logic
Stephan Kreutzer ( Oxford University Computing Laboratory )
- 16:30 29th April 2008 ( week 2, Trinity Term 2008 )Lecture Theatre A
In this talk we look at algorithmic problems on graphs, such as finding a vertex cover of a graph, or determining whether the graph can be coloured by three colours so that no edge has both endpoints coloured in the same way. Such problems have numerous applications in computer science, but in general many of these problems are NP-hard, i.e. are unlikely to be efficiently solvable on the class of all graphs.
Much effort has therefore been devoted to finding classes of graphs which on the one hand are general enough to allow interesting applications but on the other hand are restricted enough so that relevant problems can be solved efficiently. A typical example are planar graphs, which, for instance, are a useful model for road or railway maps and on which many problems that are intractable in general can be solved efficiently. Other interesting structural properties of graphs are the tree-width of graphs or other measures coming out of the graph minor theory.
In this talk we will give an introduction to this line of research. We will introduce the relevant structure properties of graphs, such as tree-width, and present some algorithms designed to work on graphs of small tree-width. The main focus will be on algorithmic meta-theorems which are results that explain good algorithmic properties for a large class of problems at once. Many of these meta-theorems are based on logical definability of algorithmic problems.
No prior knowledge of graph theory or logic is required, as all relevant methods will be properly defined and motivated.
Much effort has therefore been devoted to finding classes of graphs which on the one hand are general enough to allow interesting applications but on the other hand are restricted enough so that relevant problems can be solved efficiently. A typical example are planar graphs, which, for instance, are a useful model for road or railway maps and on which many problems that are intractable in general can be solved efficiently. Other interesting structural properties of graphs are the tree-width of graphs or other measures coming out of the graph minor theory.
In this talk we will give an introduction to this line of research. We will introduce the relevant structure properties of graphs, such as tree-width, and present some algorithms designed to work on graphs of small tree-width. The main focus will be on algorithmic meta-theorems which are results that explain good algorithmic properties for a large class of problems at once. Many of these meta-theorems are based on logical definability of algorithmic problems.
No prior knowledge of graph theory or logic is required, as all relevant methods will be properly defined and motivated.
Share this:
