Q3681950 (Q3681950): Difference between revisions
Jump to navigation
Jump to search
(Changed an Item: Edited by the infer coords bot - inferring coordiantes from postal codes) |
(Created claim: summary (P836): In the dynamic graphs community there are several approaches for the analysis on average: — incremental algorithm analysis: a data structuremaintains invariants on the dynamic graph during its evolution it is thecomplexity on average of queries to this structure that is analysed — Dynamic Erdös-Rényi model: Suppresions and additions of edges are drawn randomly at each step of time. — restricted random model: the action of adding or removing edge...) |
||||||||||||||
| Property / summary | |||||||||||||||
In the dynamic graphs community there are several approaches for the analysis on average: — incremental algorithm analysis: a data structuremaintains invariants on the dynamic graph during its evolution it is thecomplexity on average of queries to this structure that is analysed — Dynamic Erdös-Rényi model: Suppresions and additions of edges are drawn randomly at each step of time. — restricted random model: the action of adding or removing edges is decided by an opponent but the modified ridge is drawn randomly. Many work in analytical combinatorials exists around the average analysis of algorithms operating on static graphs labelled (or not). More recently, work is emerging on graph analysis with constrained labels (growth of labels along the way, repeating labels). Random generation: The state of the art is divided into three parts: ad-hoc random generators for different applications (viary networks and telecom networks), more generic algorithms (Boltzmann and Monte-Carlo method) and relatively simple to simulate random graph models (Erdös-Rényi, Watts-Strogatz and Barabási). The first part consists of contributions from LITIS, the second is a specialty of GREYC and the last part is well known to both partners. Given this common language, we want to share our expertise to improve the state of art in both communities. Algorithmic dynamic graphs: The literature on algorithms for dynamic graphs generally starts from applications and seeks to solve a specific problem related to this application. The reference paper listing the different contexts is that of Holmes (2015, in the general references). Various problems have been studied from the algorithmic point of view, including the problem of the commercial traveller, problems of waves, and more courtesy paths. There are still few contributions from the consortium on the subject, but this is just the objective of the project. Dynamic problems on graphs: Dynamic problems with graphs are of two kinds. — They can be, on the one hand, problems presented in the form of two-player games, such as the problem of gendarmes and the thief, where the game of domination. These classical problems have abundant literature linked to the recent interest in theseproblems. The difficulty of these problems lies in the fact that the solutions to the problem must be presented in the form of a strategy, hence a decision tree. Meyniel’s conjecture is one of the major challenges in graph theory.The two teams of the consortium have expertise on these problems. — they may also consist of problems for which the verification of the solution requires a dynamic, iterated calculation. This is the case, for example, with the problems of percolation, shifting guards (eternal domination) or power-domination for applications to power grids. On the latter subject, the promoter of the project was recently asked to write a book chapter. (See application file.) (English) | |||||||||||||||
| Property / summary: In the dynamic graphs community there are several approaches for the analysis on average: — incremental algorithm analysis: a data structuremaintains invariants on the dynamic graph during its evolution it is thecomplexity on average of queries to this structure that is analysed — Dynamic Erdös-Rényi model: Suppresions and additions of edges are drawn randomly at each step of time. — restricted random model: the action of adding or removing edges is decided by an opponent but the modified ridge is drawn randomly. Many work in analytical combinatorials exists around the average analysis of algorithms operating on static graphs labelled (or not). More recently, work is emerging on graph analysis with constrained labels (growth of labels along the way, repeating labels). Random generation: The state of the art is divided into three parts: ad-hoc random generators for different applications (viary networks and telecom networks), more generic algorithms (Boltzmann and Monte-Carlo method) and relatively simple to simulate random graph models (Erdös-Rényi, Watts-Strogatz and Barabási). The first part consists of contributions from LITIS, the second is a specialty of GREYC and the last part is well known to both partners. Given this common language, we want to share our expertise to improve the state of art in both communities. Algorithmic dynamic graphs: The literature on algorithms for dynamic graphs generally starts from applications and seeks to solve a specific problem related to this application. The reference paper listing the different contexts is that of Holmes (2015, in the general references). Various problems have been studied from the algorithmic point of view, including the problem of the commercial traveller, problems of waves, and more courtesy paths. There are still few contributions from the consortium on the subject, but this is just the objective of the project. Dynamic problems on graphs: Dynamic problems with graphs are of two kinds. — They can be, on the one hand, problems presented in the form of two-player games, such as the problem of gendarmes and the thief, where the game of domination. These classical problems have abundant literature linked to the recent interest in theseproblems. The difficulty of these problems lies in the fact that the solutions to the problem must be presented in the form of a strategy, hence a decision tree. Meyniel’s conjecture is one of the major challenges in graph theory.The two teams of the consortium have expertise on these problems. — they may also consist of problems for which the verification of the solution requires a dynamic, iterated calculation. This is the case, for example, with the problems of percolation, shifting guards (eternal domination) or power-domination for applications to power grids. On the latter subject, the promoter of the project was recently asked to write a book chapter. (See application file.) (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: In the dynamic graphs community there are several approaches for the analysis on average: — incremental algorithm analysis: a data structuremaintains invariants on the dynamic graph during its evolution it is thecomplexity on average of queries to this structure that is analysed — Dynamic Erdös-Rényi model: Suppresions and additions of edges are drawn randomly at each step of time. — restricted random model: the action of adding or removing edges is decided by an opponent but the modified ridge is drawn randomly. Many work in analytical combinatorials exists around the average analysis of algorithms operating on static graphs labelled (or not). More recently, work is emerging on graph analysis with constrained labels (growth of labels along the way, repeating labels). Random generation: The state of the art is divided into three parts: ad-hoc random generators for different applications (viary networks and telecom networks), more generic algorithms (Boltzmann and Monte-Carlo method) and relatively simple to simulate random graph models (Erdös-Rényi, Watts-Strogatz and Barabási). The first part consists of contributions from LITIS, the second is a specialty of GREYC and the last part is well known to both partners. Given this common language, we want to share our expertise to improve the state of art in both communities. Algorithmic dynamic graphs: The literature on algorithms for dynamic graphs generally starts from applications and seeks to solve a specific problem related to this application. The reference paper listing the different contexts is that of Holmes (2015, in the general references). Various problems have been studied from the algorithmic point of view, including the problem of the commercial traveller, problems of waves, and more courtesy paths. There are still few contributions from the consortium on the subject, but this is just the objective of the project. Dynamic problems on graphs: Dynamic problems with graphs are of two kinds. — They can be, on the one hand, problems presented in the form of two-player games, such as the problem of gendarmes and the thief, where the game of domination. These classical problems have abundant literature linked to the recent interest in theseproblems. The difficulty of these problems lies in the fact that the solutions to the problem must be presented in the form of a strategy, hence a decision tree. Meyniel’s conjecture is one of the major challenges in graph theory.The two teams of the consortium have expertise on these problems. — they may also consist of problems for which the verification of the solution requires a dynamic, iterated calculation. This is the case, for example, with the problems of percolation, shifting guards (eternal domination) or power-domination for applications to power grids. On the latter subject, the promoter of the project was recently asked to write a book chapter. (See application file.) (English) / qualifier | |||||||||||||||
point in time: 18 November 2021
| |||||||||||||||
Revision as of 18:08, 18 November 2021
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
49°29'39.59"N, 0°7'11.75"E
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
In the dynamic graphs community there are several approaches for the analysis on average: — incremental algorithm analysis: a data structuremaintains invariants on the dynamic graph during its evolution it is thecomplexity on average of queries to this structure that is analysed — Dynamic Erdös-Rényi model: Suppresions and additions of edges are drawn randomly at each step of time. — restricted random model: the action of adding or removing edges is decided by an opponent but the modified ridge is drawn randomly. Many work in analytical combinatorials exists around the average analysis of algorithms operating on static graphs labelled (or not). More recently, work is emerging on graph analysis with constrained labels (growth of labels along the way, repeating labels). Random generation: The state of the art is divided into three parts: ad-hoc random generators for different applications (viary networks and telecom networks), more generic algorithms (Boltzmann and Monte-Carlo method) and relatively simple to simulate random graph models (Erdös-Rényi, Watts-Strogatz and Barabási). The first part consists of contributions from LITIS, the second is a specialty of GREYC and the last part is well known to both partners. Given this common language, we want to share our expertise to improve the state of art in both communities. Algorithmic dynamic graphs: The literature on algorithms for dynamic graphs generally starts from applications and seeks to solve a specific problem related to this application. The reference paper listing the different contexts is that of Holmes (2015, in the general references). Various problems have been studied from the algorithmic point of view, including the problem of the commercial traveller, problems of waves, and more courtesy paths. There are still few contributions from the consortium on the subject, but this is just the objective of the project. Dynamic problems on graphs: Dynamic problems with graphs are of two kinds. — They can be, on the one hand, problems presented in the form of two-player games, such as the problem of gendarmes and the thief, where the game of domination. These classical problems have abundant literature linked to the recent interest in theseproblems. The difficulty of these problems lies in the fact that the solutions to the problem must be presented in the form of a strategy, hence a decision tree. Meyniel’s conjecture is one of the major challenges in graph theory.The two teams of the consortium have expertise on these problems. — they may also consist of problems for which the verification of the solution requires a dynamic, iterated calculation. This is the case, for example, with the problems of percolation, shifting guards (eternal domination) or power-domination for applications to power grids. On the latter subject, the promoter of the project was recently asked to write a book chapter. (See application file.) (English)
18 November 2021
0 references
Identifiers
20E06110
0 references