ERDF — ULHN — DYNET — SPRINGBOARD (Q3681950): Difference between revisions
Jump to navigation
Jump to search
(Changed label, description and/or aliases in it, and other parts: Adding Italian translations) |
(Changed label, description and/or aliases in es, and other parts: Adding Spanish translations) |
||||||||||||||
| label / es | label / es | ||||||||||||||
FEDER — ULHN — DINET — TRAMPOLÍN | |||||||||||||||
| Property / summary | |||||||||||||||
En la comunidad de gráficos dinámicos hay varios enfoques para el análisis en promedio: — análisis incremental de algoritmos: una estructura de datos mantiene invariantes en el gráfico dinámico durante su evolución es la complejidad en promedio de consultas a esta estructura que se analiza — Dynamic Erdös-Rényi model: Las supresiones y las adiciones de los bordes se dibujan aleatoriamente en cada paso del tiempo. — modelo aleatorio restringido: la acción de agregar o eliminar bordes es decidida por un oponente, pero la cresta modificada se dibuja al azar. Muchos trabajos en combinatorios analíticos existen alrededor del análisis promedio de algoritmos que operan en gráficos estáticos etiquetados (o no). Más recientemente, se está trabajando en el análisis de gráficos con etiquetas restringidas (crecimiento de etiquetas a lo largo del camino, repetición de etiquetas). Generación aleatoria: El estado de la técnica se divide en tres partes: generadores aleatorios ad-hoc para diferentes aplicaciones (redes viarias y redes de telecomunicaciones), algoritmos más genéricos (método Boltzmann y Monte-Carlo) y relativamente simples de simular modelos de gráficos aleatorios (Erdös-Rényi, Watts-Strogatz y Barabási). La primera parte consiste en contribuciones de LITIS, la segunda es una especialidad de Greyc y la última parte es bien conocida por ambos socios. Dado este lenguaje común, queremos compartir nuestra experiencia para mejorar el estado del arte en ambas comunidades. Gráficos dinámicos algorítmicos: La literatura sobre algoritmos para gráficos dinámicos generalmente parte de las aplicaciones y busca resolver un problema específico relacionado con esta aplicación. El documento de referencia que enumera los diferentes contextos es el de Holmes (2015, en las referencias generales). Varios problemas han sido estudiados desde el punto de vista algorítmico, incluyendo el problema del viajero comercial, problemas de las olas, y más caminos de cortesía. Todavía hay pocas contribuciones del consorcio sobre el tema, pero este es solo el objetivo del proyecto. Problemas dinámicos en gráficos: Los problemas dinámicos con los gráficos son de dos tipos. — Pueden ser, por un lado, problemas presentados en forma de juegos de dos jugadores, como el problema de los gendarmes y el ladrón, donde el juego de dominación. Estos problemas clásicos tienen abundante literatura vinculada al reciente interés por estos problemas. La dificultad de estos problemas radica en el hecho de que las soluciones al problema deben presentarse en forma de estrategia, de ahí un árbol de decisiones. La conjetura de Meyniel es uno de los principales desafíos en la teoría de gráficos. Los dos equipos del consorcio tienen experiencia en estos problemas. — también pueden consistir en problemas para los que la verificación de la solución requiere un cálculo dinámico e iterado. Este es el caso, por ejemplo, de los problemas de percolación, cambio de guardias (dominación eterna) o dominación de energía para aplicaciones a redes eléctricas. Sobre este último tema, recientemente se pidió al promotor del proyecto que escribiera un capítulo del libro. (Véase el expediente de solicitud.) (Spanish) | |||||||||||||||
| Property / summary: En la comunidad de gráficos dinámicos hay varios enfoques para el análisis en promedio: — análisis incremental de algoritmos: una estructura de datos mantiene invariantes en el gráfico dinámico durante su evolución es la complejidad en promedio de consultas a esta estructura que se analiza — Dynamic Erdös-Rényi model: Las supresiones y las adiciones de los bordes se dibujan aleatoriamente en cada paso del tiempo. — modelo aleatorio restringido: la acción de agregar o eliminar bordes es decidida por un oponente, pero la cresta modificada se dibuja al azar. Muchos trabajos en combinatorios analíticos existen alrededor del análisis promedio de algoritmos que operan en gráficos estáticos etiquetados (o no). Más recientemente, se está trabajando en el análisis de gráficos con etiquetas restringidas (crecimiento de etiquetas a lo largo del camino, repetición de etiquetas). Generación aleatoria: El estado de la técnica se divide en tres partes: generadores aleatorios ad-hoc para diferentes aplicaciones (redes viarias y redes de telecomunicaciones), algoritmos más genéricos (método Boltzmann y Monte-Carlo) y relativamente simples de simular modelos de gráficos aleatorios (Erdös-Rényi, Watts-Strogatz y Barabási). La primera parte consiste en contribuciones de LITIS, la segunda es una especialidad de Greyc y la última parte es bien conocida por ambos socios. Dado este lenguaje común, queremos compartir nuestra experiencia para mejorar el estado del arte en ambas comunidades. Gráficos dinámicos algorítmicos: La literatura sobre algoritmos para gráficos dinámicos generalmente parte de las aplicaciones y busca resolver un problema específico relacionado con esta aplicación. El documento de referencia que enumera los diferentes contextos es el de Holmes (2015, en las referencias generales). Varios problemas han sido estudiados desde el punto de vista algorítmico, incluyendo el problema del viajero comercial, problemas de las olas, y más caminos de cortesía. Todavía hay pocas contribuciones del consorcio sobre el tema, pero este es solo el objetivo del proyecto. Problemas dinámicos en gráficos: Los problemas dinámicos con los gráficos son de dos tipos. — Pueden ser, por un lado, problemas presentados en forma de juegos de dos jugadores, como el problema de los gendarmes y el ladrón, donde el juego de dominación. Estos problemas clásicos tienen abundante literatura vinculada al reciente interés por estos problemas. La dificultad de estos problemas radica en el hecho de que las soluciones al problema deben presentarse en forma de estrategia, de ahí un árbol de decisiones. La conjetura de Meyniel es uno de los principales desafíos en la teoría de gráficos. Los dos equipos del consorcio tienen experiencia en estos problemas. — también pueden consistir en problemas para los que la verificación de la solución requiere un cálculo dinámico e iterado. Este es el caso, por ejemplo, de los problemas de percolación, cambio de guardias (dominación eterna) o dominación de energía para aplicaciones a redes eléctricas. Sobre este último tema, recientemente se pidió al promotor del proyecto que escribiera un capítulo del libro. (Véase el expediente de solicitud.) (Spanish) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: En la comunidad de gráficos dinámicos hay varios enfoques para el análisis en promedio: — análisis incremental de algoritmos: una estructura de datos mantiene invariantes en el gráfico dinámico durante su evolución es la complejidad en promedio de consultas a esta estructura que se analiza — Dynamic Erdös-Rényi model: Las supresiones y las adiciones de los bordes se dibujan aleatoriamente en cada paso del tiempo. — modelo aleatorio restringido: la acción de agregar o eliminar bordes es decidida por un oponente, pero la cresta modificada se dibuja al azar. Muchos trabajos en combinatorios analíticos existen alrededor del análisis promedio de algoritmos que operan en gráficos estáticos etiquetados (o no). Más recientemente, se está trabajando en el análisis de gráficos con etiquetas restringidas (crecimiento de etiquetas a lo largo del camino, repetición de etiquetas). Generación aleatoria: El estado de la técnica se divide en tres partes: generadores aleatorios ad-hoc para diferentes aplicaciones (redes viarias y redes de telecomunicaciones), algoritmos más genéricos (método Boltzmann y Monte-Carlo) y relativamente simples de simular modelos de gráficos aleatorios (Erdös-Rényi, Watts-Strogatz y Barabási). La primera parte consiste en contribuciones de LITIS, la segunda es una especialidad de Greyc y la última parte es bien conocida por ambos socios. Dado este lenguaje común, queremos compartir nuestra experiencia para mejorar el estado del arte en ambas comunidades. Gráficos dinámicos algorítmicos: La literatura sobre algoritmos para gráficos dinámicos generalmente parte de las aplicaciones y busca resolver un problema específico relacionado con esta aplicación. El documento de referencia que enumera los diferentes contextos es el de Holmes (2015, en las referencias generales). Varios problemas han sido estudiados desde el punto de vista algorítmico, incluyendo el problema del viajero comercial, problemas de las olas, y más caminos de cortesía. Todavía hay pocas contribuciones del consorcio sobre el tema, pero este es solo el objetivo del proyecto. Problemas dinámicos en gráficos: Los problemas dinámicos con los gráficos son de dos tipos. — Pueden ser, por un lado, problemas presentados en forma de juegos de dos jugadores, como el problema de los gendarmes y el ladrón, donde el juego de dominación. Estos problemas clásicos tienen abundante literatura vinculada al reciente interés por estos problemas. La dificultad de estos problemas radica en el hecho de que las soluciones al problema deben presentarse en forma de estrategia, de ahí un árbol de decisiones. La conjetura de Meyniel es uno de los principales desafíos en la teoría de gráficos. Los dos equipos del consorcio tienen experiencia en estos problemas. — también pueden consistir en problemas para los que la verificación de la solución requiere un cálculo dinámico e iterado. Este es el caso, por ejemplo, de los problemas de percolación, cambio de guardias (dominación eterna) o dominación de energía para aplicaciones a redes eléctricas. Sobre este último tema, recientemente se pidió al promotor del proyecto que escribiera un capítulo del libro. (Véase el expediente de solicitud.) (Spanish) / qualifier | |||||||||||||||
point in time: 14 January 2022
| |||||||||||||||
Revision as of 01:19, 14 January 2022
Project Q3681950 in France
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | ERDF — ULHN — DYNET — SPRINGBOARD |
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
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)
1 December 2021
0 references
In de dynamische grafieken gemeenschap zijn er verschillende benaderingen voor de analyse gemiddeld: — incrementele algoritmeanalyse: een gegevensstructuur onderhoudt invarianten op de dynamische grafiek tijdens de evolutie ervan is het de complexiteit op gemiddelde van query’s aan deze structuur die wordt geanalyseerd — Dynamic Erdös-Rényi model: Suppresions en toevoegingen van randen worden willekeurig getekend bij elke stap van de tijd. — beperkt willekeurig model: de actie van het toevoegen of verwijderen van randen wordt bepaald door een tegenstander, maar de gewijzigde nok wordt willekeurig getrokken. Veel werk in analytische combinatoria bestaat rond de gemiddelde analyse van algoritmen die werken op statische grafieken (of niet). Meer recent komt er werk aan grafiekanalyse met beperkte etiketten (groei van etiketten langs de weg, het herhalen van labels). Willekeurige generatie: De stand van de techniek bestaat uit drie delen: ad-hoc random generatoren voor verschillende toepassingen (viary netwerken en telecomnetwerken), meer generieke algoritmen (Boltzmann en Monte-Carlo methode) en relatief eenvoudig om willekeurige grafiekmodellen te simuleren (Erdös-Rényi, Watts-Strogatz en Barabási). Het eerste deel bestaat uit bijdragen van LITIS, het tweede is een specialiteit van Greyc en het laatste deel is bekend bij beide partners. Gezien deze gemeenschappelijke taal willen we onze expertise delen om de stand van de techniek in beide gemeenschappen te verbeteren. Algoritmische dynamische grafieken: De literatuur over algoritmen voor dynamische grafieken begint over het algemeen bij toepassingen en probeert een specifiek probleem met betrekking tot deze toepassing op te lossen. Het referentiedocument met de verschillende contexten is dat van Holmes (2015, in de algemene referenties). Verschillende problemen zijn bestudeerd vanuit algoritmisch oogpunt, waaronder het probleem van de commerciële reiziger, problemen van golven en meer hoffelijkheidspaden. Er zijn nog weinig bijdragen van het consortium over dit onderwerp, maar dit is slechts het doel van het project. Dynamische problemen op grafieken: Dynamische problemen met grafieken zijn van twee soorten. — Het kunnen aan de ene kant problemen zijn die worden gepresenteerd in de vorm van twee-spelersspelen, zoals het probleem van gendarmes en de dief, waar het spel van overheersing. Deze klassieke problemen hebben een overvloedige literatuur die verband houdt met de recente belangstelling voor deze problemen. De moeilijkheid van deze problemen ligt in het feit dat de oplossingen voor het probleem moeten worden gepresenteerd in de vorm van een strategie, dus een beslissingsboom. Het vermoeden van Meyniel is een van de grootste uitdagingen in de grafiektheorie. De twee teams van het consortium hebben expertise over deze problemen. — zij kunnen ook bestaan uit problemen waarvoor de verificatie van de oplossing een dynamische, iterated berekening vereist. Dit is bijvoorbeeld het geval bij de problemen van percolatie, verschuivende bewakers (eeuwige overheersing) of machtsoverheersing voor toepassingen op elektriciteitsnetten. Over dit laatste onderwerp werd de promotor van het project onlangs gevraagd een boekhoofdstuk te schrijven. (Zie aanvraagdossier.) (Dutch)
6 December 2021
0 references
Nella comunità dei grafici dinamici ci sono diversi approcci per l'analisi in media: — analisi incrementale dell'algoritmo: una struttura dei dati mantiene invarianti sul grafico dinamico durante la sua evoluzione, è la complessità media delle query a questa struttura che viene analizzata — modello Dynamic Erdös-Rényi: Le soppresioni e le aggiunte di bordi sono disegnate in modo casuale in ogni fase del tempo. — modello casuale ristretto: L'azione di aggiungere o rimuovere i bordi è decisa da un avversario, ma la cresta modificata viene disegnata in modo casuale. Molti lavori in combinatorie analitiche esistono intorno all'analisi media di algoritmi che operano su grafici statici etichettati (o no). Più recentemente, sta emergendo un lavoro sull'analisi dei grafici con etichette limitate (crescita di etichette lungo il percorso, etichette ripetute). Generazione casuale: Lo stato dell'arte è diviso in tre parti: generatori casuali ad hoc per diverse applicazioni (reti viarie e reti di telecomunicazioni), algoritmi più generici (metodo Boltzmann e Monte-Carlo) e relativamente semplici da simulare modelli grafici casuali (Erdös-Rényi, Watts-Strogatz e Barabási). La prima parte è costituita da contributi della LITIS, la seconda è una specialità di Greyc e l'ultima parte è ben nota ad entrambi i partner. Dato questo linguaggio comune, vogliamo condividere le nostre competenze per migliorare lo stato dell'arte in entrambe le comunità. Grafici dinamici algoritmici: La letteratura sugli algoritmi per i grafici dinamici parte generalmente dalle applicazioni e cerca di risolvere un problema specifico relativo a questa applicazione. Il documento di riferimento che elenca i diversi contesti è quello di Holmes (2015, nei riferimenti generali). Diversi problemi sono stati studiati dal punto di vista algoritmico, tra cui il problema del viaggiatore commerciale, problemi delle onde, e più percorsi di cortesia. Sono ancora pochi i contributi del consorzio in materia, ma questo è solo l'obiettivo del progetto. Problemi dinamici sui grafici: I problemi dinamici con i grafici sono di due tipi. — Possono essere, da un lato, problemi presentati sotto forma di giochi a due giocatori, come il problema dei gendarmi e del ladro, dove il gioco del dominio. Questi problemi classici hanno un'abbondante letteratura legata al recente interesse per questiproblemi. La difficoltà di questi problemi risiede nel fatto che le soluzioni al problema devono essere presentate sotto forma di una strategia e quindi di un albero decisionale. La congettura di Meyniel è una delle principali sfide nella teoria dei grafici. I due team del consorzio hanno competenze su questi problemi. — possono anche consistere in problemi per i quali la verifica della soluzione richiede un calcolo dinamico e iterato. Questo è il caso, ad esempio, dei problemi di percolazione, di spostamento delle protezioni (dominazione eterna) o di dominazione dell'energia per le applicazioni sulle reti elettriche. Su quest'ultimo argomento, il promotore del progetto è stato recentemente invitato a scrivere un capitolo del libro. (Cfr. fascicolo di candidatura.) (Italian)
13 January 2022
0 references
En la comunidad de gráficos dinámicos hay varios enfoques para el análisis en promedio: — análisis incremental de algoritmos: una estructura de datos mantiene invariantes en el gráfico dinámico durante su evolución es la complejidad en promedio de consultas a esta estructura que se analiza — Dynamic Erdös-Rényi model: Las supresiones y las adiciones de los bordes se dibujan aleatoriamente en cada paso del tiempo. — modelo aleatorio restringido: la acción de agregar o eliminar bordes es decidida por un oponente, pero la cresta modificada se dibuja al azar. Muchos trabajos en combinatorios analíticos existen alrededor del análisis promedio de algoritmos que operan en gráficos estáticos etiquetados (o no). Más recientemente, se está trabajando en el análisis de gráficos con etiquetas restringidas (crecimiento de etiquetas a lo largo del camino, repetición de etiquetas). Generación aleatoria: El estado de la técnica se divide en tres partes: generadores aleatorios ad-hoc para diferentes aplicaciones (redes viarias y redes de telecomunicaciones), algoritmos más genéricos (método Boltzmann y Monte-Carlo) y relativamente simples de simular modelos de gráficos aleatorios (Erdös-Rényi, Watts-Strogatz y Barabási). La primera parte consiste en contribuciones de LITIS, la segunda es una especialidad de Greyc y la última parte es bien conocida por ambos socios. Dado este lenguaje común, queremos compartir nuestra experiencia para mejorar el estado del arte en ambas comunidades. Gráficos dinámicos algorítmicos: La literatura sobre algoritmos para gráficos dinámicos generalmente parte de las aplicaciones y busca resolver un problema específico relacionado con esta aplicación. El documento de referencia que enumera los diferentes contextos es el de Holmes (2015, en las referencias generales). Varios problemas han sido estudiados desde el punto de vista algorítmico, incluyendo el problema del viajero comercial, problemas de las olas, y más caminos de cortesía. Todavía hay pocas contribuciones del consorcio sobre el tema, pero este es solo el objetivo del proyecto. Problemas dinámicos en gráficos: Los problemas dinámicos con los gráficos son de dos tipos. — Pueden ser, por un lado, problemas presentados en forma de juegos de dos jugadores, como el problema de los gendarmes y el ladrón, donde el juego de dominación. Estos problemas clásicos tienen abundante literatura vinculada al reciente interés por estos problemas. La dificultad de estos problemas radica en el hecho de que las soluciones al problema deben presentarse en forma de estrategia, de ahí un árbol de decisiones. La conjetura de Meyniel es uno de los principales desafíos en la teoría de gráficos. Los dos equipos del consorcio tienen experiencia en estos problemas. — también pueden consistir en problemas para los que la verificación de la solución requiere un cálculo dinámico e iterado. Este es el caso, por ejemplo, de los problemas de percolación, cambio de guardias (dominación eterna) o dominación de energía para aplicaciones a redes eléctricas. Sobre este último tema, recientemente se pidió al promotor del proyecto que escribiera un capítulo del libro. (Véase el expediente de solicitud.) (Spanish)
14 January 2022
0 references
Identifiers
20E06110
0 references