ERDF — ULHN — DYNET — SPRINGBOARD (Q3681950)

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)

point in time

18 November 2021

0 references

In der dynamischen Graphen-Community gibt es mehrere Ansätze für die durchschnittliche Analyse: — inkrementelle Algorithmenanalyse: eine Datenstruktur unterhält Invarianten auf dem dynamischen Graph während seiner Entwicklung, es ist die durchschnittliche Komplexität der Anfragen an diese Struktur, die analysiert wird – dynamisches Erdös-Rényi-Modell: Zusätze und Kantenzusätze werden nach dem Zufallsprinzip in jedem Schritt der Zeit gezogen. — eingeschränktes Zufallsmodell: die Aktion zum Hinzufügen oder Entfernen von Kanten wird von einem Gegner entschieden, aber die modifizierte Kante wird zufällig gezogen. Viele Arbeiten in der analytischen Kombinatorik gibt es um die durchschnittliche Analyse von Algorithmen, die auf statischen Graphen arbeiten, die beschriftet werden (oder nicht). In jüngster Zeit wurden Arbeiten zur Graphenanalyse mit eingeschränkten Kennzeichnungen auf den Weg gebracht (Anstieg von Etiketten entlang des Weges, Wiederholung von Etiketten). Zufällige Erzeugung: Der Stand der Technik ist in drei Teile unterteilt: Ad-hoc-Zufallsgeneratoren für verschiedene Anwendungen (Netze und Telekommunikationsnetze), generischere Algorithmen (Boltzmann- und Monte-Carlo-Methode) und relativ einfache Zufallsgrafikmodelle (Erdös-Rényi, Watts-Strogatz und Barabási). Der erste Teil besteht aus Beiträgen des LITIS, der zweite Teil ist eine GREYC-Spezialität und der letzte Teil ist den beiden Partnern bekannt. In Anbetracht dieser gemeinsamen Sprache möchten wir daher unser Fachwissen austauschen, um den Stand der Technik in beiden Gemeinschaften zu verbessern. Algorithmische dynamische Graphen: Die Literatur über Algorithmen für dynamische Graphen geht in der Regel von Anwendungen aus und versucht, ein spezifisches Problem im Zusammenhang mit dieser Anwendung zu lösen. Das Referenzpapier, das die verschiedenen Kontexte aufzeigt, ist Holmes (2015, in den allgemeinen Referenzen). Unter algorithmischen Gesichtspunkten wurden verschiedene Probleme untersucht, darunter das Problem des Handelsreisenden, der Probleme der Flut und der Kurzstrecken. Es gibt noch wenige Beiträge des Konsortiums zu diesem Thema, aber das ist das Ziel des Projekts. Dynamische Probleme bei Graphen: Die dynamischen Probleme auf den Graphen sind zweierlei. — Sie können zum einen Probleme in Form von Spielen mit zwei Spielern sein, wie z. B. das Problem der Gendarmen und des Diebes, wo das Dominanzspiel. Diese klassischen Probleme haben eine umfangreiche Literatur, die mit dem jüngsten Interesse an diesen Problemen zusammenhängt. Die Schwierigkeit dieser Probleme liegt in der Tatsache, dass Problemlösungen in Form einer Strategie, also eines Entscheidungsbaums, dargestellt werden müssen. Meyniels Vermutung gehört zu den großen Herausforderungen in der Graphentheorie. Beide Teams des Konsortiums verfügen über Fachwissen über diese Probleme. — sie können auch aus Problemen bestehen, bei denen die Prüfung der Lösung eine dynamische, iterierte Berechnung erfordert. Dies gilt z. B. für Probleme im Zusammenhang mit Perkolation, Versetzung von Wachen (Terminal Dominanz) oder Power-Domination für Anwendungen in Stromnetzen. Zu diesem Thema wurde der Projektträger kürzlich gebeten, ein Buchkapitel zu schreiben. (Siehe Bewerbungsunterlagen) (German)

point in time

1 December 2021

0 references

Identifiers

French Kohesio ID

20E06110

0 references

ERDF — ULHN — DYNET — SPRINGBOARD (Q3681950)

Statements

Identifiers

Navigation menu

Search