No label defined (Q3681950)
Jump to navigation
Jump to search
Project Q3681950 in France
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | No label defined |
Project Q3681950 in France |
Statements
114,000.00 Euro
0 references
114,000.0 Euro
0 references
100.0 percent
0 references
31 December 2022
0 references
UNIVERSITE LE HAVRE NORMANDIE
0 references
76600
0 references
Dans la communauté graphes dynamiques plusieurs approches existent pour l'analyseen moyenne : - analyse d'algorithme incrémentaux : une structure de donnéesmaintient des invariants sur le graphe dynamique pendant son évolution c'est lacomplexité en moyenne des requêtes à cette structure qui est analysée - modèled'Erdös-Rényi dynamique : des suppresions et ajouts d'arêtes sont tirés aléatoirementà chaque étape de temps. - modèle aléatoire restreint : l'action d'ajout ou desuppression d'arêtes est décider par un adversaire mais l'arête modifiée est tiréealéatoirement. De nombreux travaux en combinatoire analytique existe autour del'analyse en moyenne d'algorithmes opérant sur des graphes statiques étiquetés (ounon). Plus récemment, des travaux émergent sur l'analyse de graphe avec desétiquetages contraints (croissance des étiquettes le long de chemin, répétitiond'étiquettes). Génération aléatoire: L'état de l'art se divise en trois parties : desgénérateurs aléatoires ad-hoc pour différentes applications (réseaux viaires etréseaux télécom), des algorithmes plus génériques (méthode de Boltzmann et deMonte-Carlo) et des modèles de graphes aléatoires relativement simples à simuler(Erdös-Rényi, Watts-Strogatz et Barabási). La première partie est composée decontributions du LITIS, la deuxième est une spécialité du GREYC et la dernière partieest bien connue des deux partenaires. Étant donné ce langage commun, nous voulonsdonc partager nos expertises pour améliorer l'état de l'art dans les deuxcommunautés. Algorithmique des graphes dynamiques : La littérature sur lesalgorithmes pour les graphes dynamiques part en général des applications et chercheà résoudre un problème spécifique lié à cette application. Le papier de référence quirépertorie les différents contextes est celui de Holmes (2015, dans les référencesgénérales). Divers problèmes ont été étudiés sous l'angle algorithmique, notamment leproblème du voyageur de commerce, des problèmes de flots, et de plus courtchemins. Il y a encore peu de contributions du consortium sur le sujet, mais c'estjustement l'objectif du projet. Problèmes dynamiques sur les graphes : Les problèmesdynamiques sur les graphes sont de deux natures. - Ils peuvent être d'une part desproblèmes présentés sous la forme de jeux à deux joueurs, comme par exemple leproblème des gendarmes et du voleur, où le jeu de domination. Ces problèmesclassiques ont une littérature abondante liée à l’intérêt récent porté sur cesproblèmes. La difficulté de ces problèmes réside dans le fait que les solutions duproblèmes doivent être présentées sous la forme d'une stratégie, donc un arbre dedécision. La conjecture de Meyniel fait partie des grands défis en théorie des graphes.Les deux équipes du consortium ont une expertise sur ces problèmes. - ils peuventaussi consister en des problèmes pour lesquels la vérification de la solution demandeun calcul dynamique, itéré. C'est par exemple le cas des problèmes de percolation, deplacement de gardes (eternal domination) ou de power-domination pour lesapplications aux réseaux électriques. Sur ce dernier sujet, le porteur du projet arécemment été sollicité pour écrire un chapitre de livre. (Cf dossier de candidature.) (French)
0 references
Identifiers
20E06110
0 references