Moteur de recherche d’entreprises européennes
Financement de l’UE (1 500 000 €) : Algorithmes et complexité des graphes distribués et dynamiques Hor14/12/2016 Programme de recherche et d'innovation de l'UE « Horizon »
Vue d’ensemble
Texte
Algorithmes et complexité des graphes distribués et dynamiques
This project aims to (i) resolve challenging graph problems in distributed and dynamic settings, with a focus on connectivity problems (such as computing edge connectivity and distances), and (ii) on the way develop a systematic approach to attack problems in these settings, by thoroughly exploring relevant algorithmic and complexity-theoretic landscapes. Tasks include - building a hierarchy of intermediate computational models so that designing algorithms and proving lower bounds can be done in several intermediate steps, - explaining the limits of algorithms by proving conditional lower bounds based on old and new reasonable conjectures, and - connecting techniques in the two settings to generate new insights that are unlikely to emerge from the isolated viewpoint of a single field. The project will take advantage from and contribute to the developments in many young fields in theoretical computer science, such as fine-grained complexity and sublinear algorithms. Resolving one of the connectivity problems will already be a groundbreaking result. However, given the approach, it is likely that one breakthrough will lead to many others.
| Kobenhavns Universitet | 237 789 € |
| Kungliga Tekniska Hoegskolan | 1 262 211 € |
https://cordis.europa.eu/project/id/715672
Cette annonce se réfère à une date antérieure et ne reflète pas nécessairement l’état actuel.
