Marx Lab

Research focus

ERC Consolidator Grant · 2016

Systematic mapping of the complexity landscape of hard algorithmic graph problems

Graph-theoretical models are natural tools for the description of road networks, circuits, communication networks, and abstract relations between objects, hence algorithmic graph problems appear in a wide range of computer science applications. As most of these problems are computationally hard in their full generality, research in graph algorithms, approximability, and parameterized complexity usually aims at identifying restricted variants and special cases, which are at the same time sufficiently general to be of practical relevance and sufficiently restricted to admit efficient algorithmic solutions. The goal of the project is to put the search for tractable algorithmic graph problems…

From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.