|
Abstract |
Many well-known graph problems such as finding vertex covers, cliques or dominating sets are easily shown to be NP complete when stated in full generality. Several approaches have be proposed to obtain feasible subproblems: One might ask for approximability (if there is a clique of size k, can we find one of size k/2?), one might restrict the set of admissible input graphs (to planar graphs, graphs of bounded tree-width etc.), or sometimes one is interested in finding relatively small cliques in large graphs, leading to the framework of parameterised complexity.
Algorithmic Meta Theorems are very general results obtained by reducing concrete algorithmic problems to model-checking problems. This allows us to develop both algorithmic techniques and complexity lower bounds applicable to a wide range of problems. |
|
Affiliation |
Kord Eickmeyer studied mathematics and computer science at the universities of Lübeck, Freiburg and Cambridge (UK) and obtained a PhD from Humboldt University Berlin, with a thesis on Randomisation in Computer Science and Logic supervised by Martin Grohe. After graduating he spent 1.5 years at the National Institute of Informatics in Tokyo with Ken-ichi Kawarabayashi. Currently he is a postdoctoral researcher at Technical University of Darmstadt. His research interests revolve around logics and computation. |
