ERDF — ULHN — DYNET — SPRINGBOARD (Q3681950): Difference between revisions
Jump to navigation
Jump to search
(Removed claim: summary (P836): Dans la communauté graphes dynamiques plusieurs approches existent pour l’analyseen moyenne: — Analyse von d’algorithme incrémentaux: une structure de donnéesmaintient des invariants sur le graphe dynamique hang 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 restrei...) |
(Changed label, description and/or aliases in pt) |
||||||||||||||
| (9 intermediate revisions by 2 users not shown) | |||||||||||||||
| label / nl | label / nl | ||||||||||||||
EFRO — ULHN — DYNET — SPRINGPLANK | |||||||||||||||
| label / it | label / it | ||||||||||||||
FESR — ULHN — DYNET — TRAMPOLINO DI LANCIO | |||||||||||||||
| label / es | label / es | ||||||||||||||
FEDER — ULHN — DINET — TRAMPOLÍN | |||||||||||||||
| label / et | label / et | ||||||||||||||
ERF – ULHN – DYNET – HÜPPELAUD | |||||||||||||||
| label / lt | label / lt | ||||||||||||||
ERPF – ULHN – DYNET – TRAMPLINAS | |||||||||||||||
| label / hr | label / hr | ||||||||||||||
EFRR – ULHN – DYNET – ODSKOČNA DASKA | |||||||||||||||
| label / el | label / el | ||||||||||||||
ΕΤΠΑ — ULHN — DYNET — ΕΦΑΛΤΉΡΙΟ | |||||||||||||||
| label / sk | label / sk | ||||||||||||||
EFRR – ULHN – DYNET – ODRAZOVÝ MOSTÍK | |||||||||||||||
| label / fi | label / fi | ||||||||||||||
EAKR – ULHN – DYNETTI – PONNAHDUSLAUTA | |||||||||||||||
| label / pl | label / pl | ||||||||||||||
EFRR – ULHN – DYNET – TRAMPOLINA | |||||||||||||||
| label / hu | label / hu | ||||||||||||||
ERFA – ULHN – DYNET – UGRÓDESZKA | |||||||||||||||
| label / cs | label / cs | ||||||||||||||
EFRR – ULHN – DYNET – ODRAZOVÝ MŮSTEK | |||||||||||||||
| label / lv | label / lv | ||||||||||||||
ERAF — ULHN — DYNET — ATSPĒRIENA PUNKTS | |||||||||||||||
| label / ga | label / ga | ||||||||||||||
CFRE — ULHN — DYNET — SPRINGBOARD | |||||||||||||||
| label / sl | label / sl | ||||||||||||||
ESRR – ULHN – DINET – ODSKOČNA DESKA | |||||||||||||||
| label / bg | label / bg | ||||||||||||||
ЕФРР — ULHN — ДИНЕТ — ТРАМПЛИН | |||||||||||||||
| label / mt | label / mt | ||||||||||||||
ERDF — ULHN — DYNET — KATALISTA | |||||||||||||||
| label / pt | label / pt | ||||||||||||||
FEDER — ULHN — DYNET — SPRINGBOARD | |||||||||||||||
| label / da | label / da | ||||||||||||||
EFRU — ULHN — DYNE — SPRINGBRÆT | |||||||||||||||
| label / ro | label / ro | ||||||||||||||
FEDR – ULHN – DYNET – RAMPĂ DE LANSARE | |||||||||||||||
| label / sv | label / sv | ||||||||||||||
ERUF – ULHN – DYNET – SPRÅNGBRÄDA | |||||||||||||||
| description / bg | description / bg | ||||||||||||||
Проект Q3681950 във Франция | |||||||||||||||
| description / hr | description / hr | ||||||||||||||
Projekt Q3681950 u Francuskoj | |||||||||||||||
| description / hu | description / hu | ||||||||||||||
Projekt Q3681950 Franciaországban | |||||||||||||||
| description / cs | description / cs | ||||||||||||||
Projekt Q3681950 ve Francii | |||||||||||||||
| description / da | description / da | ||||||||||||||
Projekt Q3681950 i Frankrig | |||||||||||||||
| description / nl | description / nl | ||||||||||||||
Project Q3681950 in Frankrijk | |||||||||||||||
| description / et | description / et | ||||||||||||||
Projekt Q3681950 Prantsusmaal | |||||||||||||||
| description / fi | description / fi | ||||||||||||||
Projekti Q3681950 Ranskassa | |||||||||||||||
| description / fr | description / fr | ||||||||||||||
Projet Q3681950 en France | |||||||||||||||
| description / de | description / de | ||||||||||||||
Projekt Q3681950 in Frankreich | |||||||||||||||
| description / el | description / el | ||||||||||||||
Έργο Q3681950 στη Γαλλία | |||||||||||||||
| description / ga | description / ga | ||||||||||||||
Tionscadal Q3681950 sa Fhrainc | |||||||||||||||
| description / it | description / it | ||||||||||||||
Progetto Q3681950 in Francia | |||||||||||||||
| description / lv | description / lv | ||||||||||||||
Projekts Q3681950 Francijā | |||||||||||||||
| description / lt | description / lt | ||||||||||||||
Projektas Q3681950 Prancūzijoje | |||||||||||||||
| description / mt | description / mt | ||||||||||||||
Proġett Q3681950 fi Franza | |||||||||||||||
| description / pl | description / pl | ||||||||||||||
Projekt Q3681950 we Francji | |||||||||||||||
| description / pt | description / pt | ||||||||||||||
Projeto Q3681950 na França | |||||||||||||||
| description / ro | description / ro | ||||||||||||||
Proiectul Q3681950 în Franța | |||||||||||||||
| description / sk | description / sk | ||||||||||||||
Projekt Q3681950 vo Francúzsku | |||||||||||||||
| description / sl | description / sl | ||||||||||||||
Projekt Q3681950 v Franciji | |||||||||||||||
| description / es | description / es | ||||||||||||||
Proyecto Q3681950 en Francia | |||||||||||||||
| description / sv | description / sv | ||||||||||||||
Projekt Q3681950 i Frankrike | |||||||||||||||
| Property / end time | |||||||||||||||
| |||||||||||||||
| Property / end time: 31 December 2022 / rank | |||||||||||||||
| Property / beneficiary name (string) | |||||||||||||||
| Property / beneficiary name (string): UNIVERSITE LE HAVRE NORMANDIE / 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 | |||||||||||||||
readability score: 0.1523171731679524
| |||||||||||||||
| Property / postal code | |||||||||||||||
| Property / postal code: 76600 / rank | |||||||||||||||
| Property / coordinate location | |||||||||||||||
| |||||||||||||||
| Property / coordinate location: 49°29'39.59"N, 0°7'11.75"E / rank | |||||||||||||||
| Property / contained in NUTS | |||||||||||||||
| Property / contained in NUTS: Seine-Maritime / rank | |||||||||||||||
| Property / beneficiary | |||||||||||||||
| Property / beneficiary: Q3766898 / rank | |||||||||||||||
| Property / summary | |||||||||||||||
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) | |||||||||||||||
| Property / summary: 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) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: 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) / qualifier | |||||||||||||||
point in time: 1 December 2021
| |||||||||||||||
| Property / summary | |||||||||||||||
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) | |||||||||||||||
| Property / summary: 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) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: 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) / qualifier | |||||||||||||||
point in time: 6 December 2021
| |||||||||||||||
| Property / summary | |||||||||||||||
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) | |||||||||||||||
| Property / summary: 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) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: 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) / qualifier | |||||||||||||||
point in time: 13 January 2022
| |||||||||||||||
| 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
| |||||||||||||||
| Property / summary | |||||||||||||||
Dünaamiliste graafikute kogukonnas on analüüsi jaoks keskmiselt mitu lähenemisviisi: – täiendavate algoritmide analüüs: andmestruktuur säilitab dünaamilise graafiku invariants arengu ajal on analüüsitud selle struktuuri kohta keskmiselt päringute tegemise keerukus – Dynamic Erdös-Rényi mudel: Tarned ja täiendused servad on koostatud juhuslikult igal sammul. – piiratud juhumudel: servade lisamise või eemaldamise toimingu otsustab vastane, kuid modifitseeritud servad tõmmatakse juhuslikult. Paljud tööd analüütiline kombinatorials olemas umbes keskmine analüüs algoritmid töötavad staatiline graafikud märgistatud (või mitte). Viimasel ajal on käimas töö graafikute analüüsiga, mis hõlmab piiratud märgiseid (märgiste kasv teel, siltide kordamine). Juhuslik põlvkond: Tehnika tase on jagatud kolme ossa: ad hoc juhuslikud generaatorid erinevate rakenduste jaoks (viraalvõrgud ja telekommunikatsioonivõrgud), üldisemad algoritmid (Boltzmanni ja Monte-Carlo meetod) ning suhteliselt lihtsad juhusliku graafiku mudelid (Erdös-Rényi, Watts-Strogatz ja Barabási). Esimene osa koosneb LITISe panusest, teine Greyci erialast ja viimane osa on mõlemale partnerile hästi teada. Arvestades seda ühist keelt, soovime jagada oma teadmisi, et parandada mõlema kogukonna tehnika taset. Algoritmilised dünaamilised graafikud: Dünaamilise graafiku algoritme käsitlev kirjandus algab üldiselt rakendustest ja püüab lahendada selle rakendusega seotud konkreetset probleemi. Viitedokument, milles on loetletud erinevad kontekstid, on Holmesi oma (2015, üldviidetes). Algoritmilisest vaatepunktist on uuritud erinevaid probleeme, sealhulgas kommertsreisija probleemi, lainete probleeme ja rohkem viisakaid teid. Konsortsium on selles küsimuses veel vähe kaastööd teinud, kuid see on vaid projekti eesmärk. Dünaamilised probleemid graafikutel: Dünaamilised probleemid graafikutega on kahte liiki. – Need võivad ühelt poolt olla kahe mängijaga mängude kujul esitatud probleemid, nagu sandarme ja varas, kus domineerimine toimub. Need klassikalised probleemid on rikkalik kirjandus, mis on seotud hiljutise huviga nende probleemide vastu. Nende probleemide raskus seisneb selles, et probleemi lahendused tuleb esitada strateegia kujul, seega otsustamisskeemina. Meyniel oletuste on üks peamisi väljakutseid graafik teooria.Kaks meeskonda konsortsiumi on teadmisi nende probleemide. – need võivad koosneda ka probleemidest, mille puhul lahenduse kontrollimine nõuab dünaamilist itereeritud arvutust. Nii on see näiteks perkolatsiooni, kaitsepiirete nihutamise (igavene domineerimine) või elektrivõrkudesse tehtavate rakenduste elektridomeenimisega seotud probleemide puhul. Viimati nimetatud teemal paluti projekti elluviijal hiljuti kirjutada raamatupeatükk. (Vt taotlustoimikut.) (Estonian) | |||||||||||||||
| Property / summary: Dünaamiliste graafikute kogukonnas on analüüsi jaoks keskmiselt mitu lähenemisviisi: – täiendavate algoritmide analüüs: andmestruktuur säilitab dünaamilise graafiku invariants arengu ajal on analüüsitud selle struktuuri kohta keskmiselt päringute tegemise keerukus – Dynamic Erdös-Rényi mudel: Tarned ja täiendused servad on koostatud juhuslikult igal sammul. – piiratud juhumudel: servade lisamise või eemaldamise toimingu otsustab vastane, kuid modifitseeritud servad tõmmatakse juhuslikult. Paljud tööd analüütiline kombinatorials olemas umbes keskmine analüüs algoritmid töötavad staatiline graafikud märgistatud (või mitte). Viimasel ajal on käimas töö graafikute analüüsiga, mis hõlmab piiratud märgiseid (märgiste kasv teel, siltide kordamine). Juhuslik põlvkond: Tehnika tase on jagatud kolme ossa: ad hoc juhuslikud generaatorid erinevate rakenduste jaoks (viraalvõrgud ja telekommunikatsioonivõrgud), üldisemad algoritmid (Boltzmanni ja Monte-Carlo meetod) ning suhteliselt lihtsad juhusliku graafiku mudelid (Erdös-Rényi, Watts-Strogatz ja Barabási). Esimene osa koosneb LITISe panusest, teine Greyci erialast ja viimane osa on mõlemale partnerile hästi teada. Arvestades seda ühist keelt, soovime jagada oma teadmisi, et parandada mõlema kogukonna tehnika taset. Algoritmilised dünaamilised graafikud: Dünaamilise graafiku algoritme käsitlev kirjandus algab üldiselt rakendustest ja püüab lahendada selle rakendusega seotud konkreetset probleemi. Viitedokument, milles on loetletud erinevad kontekstid, on Holmesi oma (2015, üldviidetes). Algoritmilisest vaatepunktist on uuritud erinevaid probleeme, sealhulgas kommertsreisija probleemi, lainete probleeme ja rohkem viisakaid teid. Konsortsium on selles küsimuses veel vähe kaastööd teinud, kuid see on vaid projekti eesmärk. Dünaamilised probleemid graafikutel: Dünaamilised probleemid graafikutega on kahte liiki. – Need võivad ühelt poolt olla kahe mängijaga mängude kujul esitatud probleemid, nagu sandarme ja varas, kus domineerimine toimub. Need klassikalised probleemid on rikkalik kirjandus, mis on seotud hiljutise huviga nende probleemide vastu. Nende probleemide raskus seisneb selles, et probleemi lahendused tuleb esitada strateegia kujul, seega otsustamisskeemina. Meyniel oletuste on üks peamisi väljakutseid graafik teooria.Kaks meeskonda konsortsiumi on teadmisi nende probleemide. – need võivad koosneda ka probleemidest, mille puhul lahenduse kontrollimine nõuab dünaamilist itereeritud arvutust. Nii on see näiteks perkolatsiooni, kaitsepiirete nihutamise (igavene domineerimine) või elektrivõrkudesse tehtavate rakenduste elektridomeenimisega seotud probleemide puhul. Viimati nimetatud teemal paluti projekti elluviijal hiljuti kirjutada raamatupeatükk. (Vt taotlustoimikut.) (Estonian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Dünaamiliste graafikute kogukonnas on analüüsi jaoks keskmiselt mitu lähenemisviisi: – täiendavate algoritmide analüüs: andmestruktuur säilitab dünaamilise graafiku invariants arengu ajal on analüüsitud selle struktuuri kohta keskmiselt päringute tegemise keerukus – Dynamic Erdös-Rényi mudel: Tarned ja täiendused servad on koostatud juhuslikult igal sammul. – piiratud juhumudel: servade lisamise või eemaldamise toimingu otsustab vastane, kuid modifitseeritud servad tõmmatakse juhuslikult. Paljud tööd analüütiline kombinatorials olemas umbes keskmine analüüs algoritmid töötavad staatiline graafikud märgistatud (või mitte). Viimasel ajal on käimas töö graafikute analüüsiga, mis hõlmab piiratud märgiseid (märgiste kasv teel, siltide kordamine). Juhuslik põlvkond: Tehnika tase on jagatud kolme ossa: ad hoc juhuslikud generaatorid erinevate rakenduste jaoks (viraalvõrgud ja telekommunikatsioonivõrgud), üldisemad algoritmid (Boltzmanni ja Monte-Carlo meetod) ning suhteliselt lihtsad juhusliku graafiku mudelid (Erdös-Rényi, Watts-Strogatz ja Barabási). Esimene osa koosneb LITISe panusest, teine Greyci erialast ja viimane osa on mõlemale partnerile hästi teada. Arvestades seda ühist keelt, soovime jagada oma teadmisi, et parandada mõlema kogukonna tehnika taset. Algoritmilised dünaamilised graafikud: Dünaamilise graafiku algoritme käsitlev kirjandus algab üldiselt rakendustest ja püüab lahendada selle rakendusega seotud konkreetset probleemi. Viitedokument, milles on loetletud erinevad kontekstid, on Holmesi oma (2015, üldviidetes). Algoritmilisest vaatepunktist on uuritud erinevaid probleeme, sealhulgas kommertsreisija probleemi, lainete probleeme ja rohkem viisakaid teid. Konsortsium on selles küsimuses veel vähe kaastööd teinud, kuid see on vaid projekti eesmärk. Dünaamilised probleemid graafikutel: Dünaamilised probleemid graafikutega on kahte liiki. – Need võivad ühelt poolt olla kahe mängijaga mängude kujul esitatud probleemid, nagu sandarme ja varas, kus domineerimine toimub. Need klassikalised probleemid on rikkalik kirjandus, mis on seotud hiljutise huviga nende probleemide vastu. Nende probleemide raskus seisneb selles, et probleemi lahendused tuleb esitada strateegia kujul, seega otsustamisskeemina. Meyniel oletuste on üks peamisi väljakutseid graafik teooria.Kaks meeskonda konsortsiumi on teadmisi nende probleemide. – need võivad koosneda ka probleemidest, mille puhul lahenduse kontrollimine nõuab dünaamilist itereeritud arvutust. Nii on see näiteks perkolatsiooni, kaitsepiirete nihutamise (igavene domineerimine) või elektrivõrkudesse tehtavate rakenduste elektridomeenimisega seotud probleemide puhul. Viimati nimetatud teemal paluti projekti elluviijal hiljuti kirjutada raamatupeatükk. (Vt taotlustoimikut.) (Estonian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
Dinaminių grafikų bendruomenėje yra keli analizės metodai: – papildomo algoritmo analizė: duomenų struktūra išlaiko kintamuosius dinaminio grafiko metu, tai yra vidutiniškai sudėtingų užklausų į šią struktūrą, kuri yra analizuojama – Dynamic Erdös-Rényi modelis: Suppresions ir papildymai kraštų yra atsitiktine tvarka kiekviename laiko etape. – ribotas atsitiktinis modelis: iš pridedant arba pašalinant kraštų veiksmų nusprendžia priešininkas, bet modifikuota ketera yra sudarytas atsitiktine tvarka. Daug darbo analitinių derinių srityje yra apie vidutinę algoritmų, veikiančių ant statinių grafikų (arba ne), analizę. Pastaruoju metu pradedamas darbas grafiko analizės srityje, naudojant suvaržytas etiketes (ženklų augimas pakeliui, etikečių kartojimas). Atsitiktinė generacija: Naujausias technikos lygis suskirstytas į tris dalis: ad hoc atsitiktiniai generatoriai įvairioms reikmėms (viariniai tinklai ir telekomunikacijų tinklai), bendresni algoritmai (Boltzmann ir Monte-Carlo metodas) ir palyginti paprasti atsitiktinių grafikų modeliai (Erdös-Rényi, Watts-Strogatz ir Barabįsi). Pirmąją dalį sudaro LITIS įnašai, antroji – Greyc specialybė, o paskutinė dalis gerai žinoma abiem partneriams. Atsižvelgdami į šią bendrą kalbą, norime pasidalinti savo patirtimi, kad būtų pagerintas abiejų bendruomenių modernumas. Algoritminiai dinaminiai grafikai: Literatūra apie dinaminių grafikų algoritmus paprastai prasideda nuo taikomųjų programų ir ja siekiama išspręsti konkrečią su šia programa susijusią problemą. Informacinis dokumentas, kuriame išvardijami skirtingi kontekstai, yra Holmes (2015 m. bendrosiose nuorodose). Algoritminiu požiūriu buvo ištirtos įvairios problemos, įskaitant komercinio keliautojo problemą, bangų problemas ir daugiau mandagumo takų. Šiuo klausimu konsorciumas vis dar mažai prisidėjo, tačiau tai yra tik projekto tikslas. Dinaminės problemos diagramose: Dinaminės problemos su grafikais yra dviejų rūšių. – Jie gali būti, viena vertus, problemų, pateiktų dviejų žaidėjų žaidimų forma, pavyzdžiui, žandarmų ir vagio problema, kur dominavimo žaidimas. Šios klasikinės problemos turi gausybę literatūros, susijusios su pastarojo meto susidomėjimu šiomis problemomis. Šių problemų sudėtingumas susijęs su tuo, kad problemos sprendimai turi būti pateikti strategijos, taigi ir sprendimų medžio, forma. Meyniel hipotezė yra vienas iš pagrindinių iššūkių grafikos teorijoje. Dvi konsorciumo komandos turi žinių apie šias problemas. – jie taip pat gali būti susiję su problemomis, kurių sprendimui patikrinti reikalingas dinaminis kartotinis skaičiavimas. Taip yra, pavyzdžiui, dėl prasiskverbimo, apsaugų perkėlimo (amžinojo dominavimo) ar elektros energijos dominavimo į elektros tinklus. Pastaruoju metu projekto rengėjo buvo paprašyta parašyti knygos skyrių. (Žr. paraiškos bylą.) (Lithuanian) | |||||||||||||||
| Property / summary: Dinaminių grafikų bendruomenėje yra keli analizės metodai: – papildomo algoritmo analizė: duomenų struktūra išlaiko kintamuosius dinaminio grafiko metu, tai yra vidutiniškai sudėtingų užklausų į šią struktūrą, kuri yra analizuojama – Dynamic Erdös-Rényi modelis: Suppresions ir papildymai kraštų yra atsitiktine tvarka kiekviename laiko etape. – ribotas atsitiktinis modelis: iš pridedant arba pašalinant kraštų veiksmų nusprendžia priešininkas, bet modifikuota ketera yra sudarytas atsitiktine tvarka. Daug darbo analitinių derinių srityje yra apie vidutinę algoritmų, veikiančių ant statinių grafikų (arba ne), analizę. Pastaruoju metu pradedamas darbas grafiko analizės srityje, naudojant suvaržytas etiketes (ženklų augimas pakeliui, etikečių kartojimas). Atsitiktinė generacija: Naujausias technikos lygis suskirstytas į tris dalis: ad hoc atsitiktiniai generatoriai įvairioms reikmėms (viariniai tinklai ir telekomunikacijų tinklai), bendresni algoritmai (Boltzmann ir Monte-Carlo metodas) ir palyginti paprasti atsitiktinių grafikų modeliai (Erdös-Rényi, Watts-Strogatz ir Barabįsi). Pirmąją dalį sudaro LITIS įnašai, antroji – Greyc specialybė, o paskutinė dalis gerai žinoma abiem partneriams. Atsižvelgdami į šią bendrą kalbą, norime pasidalinti savo patirtimi, kad būtų pagerintas abiejų bendruomenių modernumas. Algoritminiai dinaminiai grafikai: Literatūra apie dinaminių grafikų algoritmus paprastai prasideda nuo taikomųjų programų ir ja siekiama išspręsti konkrečią su šia programa susijusią problemą. Informacinis dokumentas, kuriame išvardijami skirtingi kontekstai, yra Holmes (2015 m. bendrosiose nuorodose). Algoritminiu požiūriu buvo ištirtos įvairios problemos, įskaitant komercinio keliautojo problemą, bangų problemas ir daugiau mandagumo takų. Šiuo klausimu konsorciumas vis dar mažai prisidėjo, tačiau tai yra tik projekto tikslas. Dinaminės problemos diagramose: Dinaminės problemos su grafikais yra dviejų rūšių. – Jie gali būti, viena vertus, problemų, pateiktų dviejų žaidėjų žaidimų forma, pavyzdžiui, žandarmų ir vagio problema, kur dominavimo žaidimas. Šios klasikinės problemos turi gausybę literatūros, susijusios su pastarojo meto susidomėjimu šiomis problemomis. Šių problemų sudėtingumas susijęs su tuo, kad problemos sprendimai turi būti pateikti strategijos, taigi ir sprendimų medžio, forma. Meyniel hipotezė yra vienas iš pagrindinių iššūkių grafikos teorijoje. Dvi konsorciumo komandos turi žinių apie šias problemas. – jie taip pat gali būti susiję su problemomis, kurių sprendimui patikrinti reikalingas dinaminis kartotinis skaičiavimas. Taip yra, pavyzdžiui, dėl prasiskverbimo, apsaugų perkėlimo (amžinojo dominavimo) ar elektros energijos dominavimo į elektros tinklus. Pastaruoju metu projekto rengėjo buvo paprašyta parašyti knygos skyrių. (Žr. paraiškos bylą.) (Lithuanian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Dinaminių grafikų bendruomenėje yra keli analizės metodai: – papildomo algoritmo analizė: duomenų struktūra išlaiko kintamuosius dinaminio grafiko metu, tai yra vidutiniškai sudėtingų užklausų į šią struktūrą, kuri yra analizuojama – Dynamic Erdös-Rényi modelis: Suppresions ir papildymai kraštų yra atsitiktine tvarka kiekviename laiko etape. – ribotas atsitiktinis modelis: iš pridedant arba pašalinant kraštų veiksmų nusprendžia priešininkas, bet modifikuota ketera yra sudarytas atsitiktine tvarka. Daug darbo analitinių derinių srityje yra apie vidutinę algoritmų, veikiančių ant statinių grafikų (arba ne), analizę. Pastaruoju metu pradedamas darbas grafiko analizės srityje, naudojant suvaržytas etiketes (ženklų augimas pakeliui, etikečių kartojimas). Atsitiktinė generacija: Naujausias technikos lygis suskirstytas į tris dalis: ad hoc atsitiktiniai generatoriai įvairioms reikmėms (viariniai tinklai ir telekomunikacijų tinklai), bendresni algoritmai (Boltzmann ir Monte-Carlo metodas) ir palyginti paprasti atsitiktinių grafikų modeliai (Erdös-Rényi, Watts-Strogatz ir Barabįsi). Pirmąją dalį sudaro LITIS įnašai, antroji – Greyc specialybė, o paskutinė dalis gerai žinoma abiem partneriams. Atsižvelgdami į šią bendrą kalbą, norime pasidalinti savo patirtimi, kad būtų pagerintas abiejų bendruomenių modernumas. Algoritminiai dinaminiai grafikai: Literatūra apie dinaminių grafikų algoritmus paprastai prasideda nuo taikomųjų programų ir ja siekiama išspręsti konkrečią su šia programa susijusią problemą. Informacinis dokumentas, kuriame išvardijami skirtingi kontekstai, yra Holmes (2015 m. bendrosiose nuorodose). Algoritminiu požiūriu buvo ištirtos įvairios problemos, įskaitant komercinio keliautojo problemą, bangų problemas ir daugiau mandagumo takų. Šiuo klausimu konsorciumas vis dar mažai prisidėjo, tačiau tai yra tik projekto tikslas. Dinaminės problemos diagramose: Dinaminės problemos su grafikais yra dviejų rūšių. – Jie gali būti, viena vertus, problemų, pateiktų dviejų žaidėjų žaidimų forma, pavyzdžiui, žandarmų ir vagio problema, kur dominavimo žaidimas. Šios klasikinės problemos turi gausybę literatūros, susijusios su pastarojo meto susidomėjimu šiomis problemomis. Šių problemų sudėtingumas susijęs su tuo, kad problemos sprendimai turi būti pateikti strategijos, taigi ir sprendimų medžio, forma. Meyniel hipotezė yra vienas iš pagrindinių iššūkių grafikos teorijoje. Dvi konsorciumo komandos turi žinių apie šias problemas. – jie taip pat gali būti susiję su problemomis, kurių sprendimui patikrinti reikalingas dinaminis kartotinis skaičiavimas. Taip yra, pavyzdžiui, dėl prasiskverbimo, apsaugų perkėlimo (amžinojo dominavimo) ar elektros energijos dominavimo į elektros tinklus. Pastaruoju metu projekto rengėjo buvo paprašyta parašyti knygos skyrių. (Žr. paraiškos bylą.) (Lithuanian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
U zajednici s dinamičkim grafikonima postoji nekoliko pristupa za analizu u prosjeku: — inkrementalna analiza algoritma: struktura podataka zadržava invarijante na dinamičkom grafikonu tijekom njegove evolucije, analizirana je složenost u prosjeku upita za tu strukturu – dinamički Erdös-Rényi model: Suppresions i dodaci rubova su nacrtani nasumično u svakom koraku vremena. — ograničeni slučajni model: djelovanje dodavanja ili uklanjanja rubova odlučuje protivnik, ali modificirani greben je nacrtan nasumce. Mnogi rade u analitičkim kombinatorima oko prosječne analize algoritama koji rade na statičkim grafovima označenim (ili ne). U novije vrijeme pojavljuje se rad na analizi grafikona s ograničenim oznakama (rast oznaka na putu, ponavljanje oznaka). Nasumična generacija: Stanje tehnike podijeljeno je na tri dijela: ad hoc nasumični generatori za različite primjene (mreže za ptice i telekomunikacijske mreže), općenitiji algoritmi (metoda Boltzmann i Monte-Carlo) i relativno jednostavni za simulaciju nasumičnih grafičkih modela (Erdös-Rényi, Watts-Strogatz i Barabási). Prvi dio se sastoji od doprinosa iz LITIS, drugi je specijalnost Greyc i posljednji dio je dobro poznat oba partnera. S obzirom na taj zajednički jezik želimo podijeliti svoje stručno znanje kako bismo poboljšali najnovija dostignuća u objema zajednicama. Algoritamski dinamički grafikoni: Literatura o algoritmima za dinamičke grafove općenito počinje od aplikacija i nastoji riješiti određeni problem povezan s ovom aplikacijom. Referentni dokument u kojem su navedeni različiti konteksti nalazi se u Holmesu (2015., u općim referencama). Proučavani su različiti problemi s algoritamskog stajališta, uključujući problem komercijalnog putnika, probleme valova i više ljubaznosti. Još uvijek postoji malo doprinosa konzorcija o toj temi, ali to je samo cilj projekta. Dinamički problemi na grafikonima: Dinamički problemi sa grafovima su dvije vrste. — Oni mogu biti, s jedne strane, problemi predstavljeni u obliku dva igrača igre, kao što je problem žandarmes i lopov, gdje igra dominacije. Ovi klasični problemi imaju bogatu literaturu povezanu s nedavnim interesom za oveprobleme. Poteškoće tih problema leži u činjenici da rješenja problema moraju biti predstavljena u obliku strategije, a time i stabla odlučivanja. Meyniel je pretpostavka je jedan od glavnih izazova u teorija graf.The dva tima konzorcija imaju stručnost o tim problemima. — mogu se sastojati i od problema za koje provjera rješenja zahtijeva dinamičan, iterirani izračun. To je, na primjer, slučaj s problemima perkolacije, pomicanja čuvara (vječne dominacije) ili dominacije energije za primjene u elektroenergetskim mrežama. Na potonju temu, promotor projekta nedavno je zamoljen da napiše poglavlje knjige. (Vidjeti datoteku zahtjeva.) (Croatian) | |||||||||||||||
| Property / summary: U zajednici s dinamičkim grafikonima postoji nekoliko pristupa za analizu u prosjeku: — inkrementalna analiza algoritma: struktura podataka zadržava invarijante na dinamičkom grafikonu tijekom njegove evolucije, analizirana je složenost u prosjeku upita za tu strukturu – dinamički Erdös-Rényi model: Suppresions i dodaci rubova su nacrtani nasumično u svakom koraku vremena. — ograničeni slučajni model: djelovanje dodavanja ili uklanjanja rubova odlučuje protivnik, ali modificirani greben je nacrtan nasumce. Mnogi rade u analitičkim kombinatorima oko prosječne analize algoritama koji rade na statičkim grafovima označenim (ili ne). U novije vrijeme pojavljuje se rad na analizi grafikona s ograničenim oznakama (rast oznaka na putu, ponavljanje oznaka). Nasumična generacija: Stanje tehnike podijeljeno je na tri dijela: ad hoc nasumični generatori za različite primjene (mreže za ptice i telekomunikacijske mreže), općenitiji algoritmi (metoda Boltzmann i Monte-Carlo) i relativno jednostavni za simulaciju nasumičnih grafičkih modela (Erdös-Rényi, Watts-Strogatz i Barabási). Prvi dio se sastoji od doprinosa iz LITIS, drugi je specijalnost Greyc i posljednji dio je dobro poznat oba partnera. S obzirom na taj zajednički jezik želimo podijeliti svoje stručno znanje kako bismo poboljšali najnovija dostignuća u objema zajednicama. Algoritamski dinamički grafikoni: Literatura o algoritmima za dinamičke grafove općenito počinje od aplikacija i nastoji riješiti određeni problem povezan s ovom aplikacijom. Referentni dokument u kojem su navedeni različiti konteksti nalazi se u Holmesu (2015., u općim referencama). Proučavani su različiti problemi s algoritamskog stajališta, uključujući problem komercijalnog putnika, probleme valova i više ljubaznosti. Još uvijek postoji malo doprinosa konzorcija o toj temi, ali to je samo cilj projekta. Dinamički problemi na grafikonima: Dinamički problemi sa grafovima su dvije vrste. — Oni mogu biti, s jedne strane, problemi predstavljeni u obliku dva igrača igre, kao što je problem žandarmes i lopov, gdje igra dominacije. Ovi klasični problemi imaju bogatu literaturu povezanu s nedavnim interesom za oveprobleme. Poteškoće tih problema leži u činjenici da rješenja problema moraju biti predstavljena u obliku strategije, a time i stabla odlučivanja. Meyniel je pretpostavka je jedan od glavnih izazova u teorija graf.The dva tima konzorcija imaju stručnost o tim problemima. — mogu se sastojati i od problema za koje provjera rješenja zahtijeva dinamičan, iterirani izračun. To je, na primjer, slučaj s problemima perkolacije, pomicanja čuvara (vječne dominacije) ili dominacije energije za primjene u elektroenergetskim mrežama. Na potonju temu, promotor projekta nedavno je zamoljen da napiše poglavlje knjige. (Vidjeti datoteku zahtjeva.) (Croatian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: U zajednici s dinamičkim grafikonima postoji nekoliko pristupa za analizu u prosjeku: — inkrementalna analiza algoritma: struktura podataka zadržava invarijante na dinamičkom grafikonu tijekom njegove evolucije, analizirana je složenost u prosjeku upita za tu strukturu – dinamički Erdös-Rényi model: Suppresions i dodaci rubova su nacrtani nasumično u svakom koraku vremena. — ograničeni slučajni model: djelovanje dodavanja ili uklanjanja rubova odlučuje protivnik, ali modificirani greben je nacrtan nasumce. Mnogi rade u analitičkim kombinatorima oko prosječne analize algoritama koji rade na statičkim grafovima označenim (ili ne). U novije vrijeme pojavljuje se rad na analizi grafikona s ograničenim oznakama (rast oznaka na putu, ponavljanje oznaka). Nasumična generacija: Stanje tehnike podijeljeno je na tri dijela: ad hoc nasumični generatori za različite primjene (mreže za ptice i telekomunikacijske mreže), općenitiji algoritmi (metoda Boltzmann i Monte-Carlo) i relativno jednostavni za simulaciju nasumičnih grafičkih modela (Erdös-Rényi, Watts-Strogatz i Barabási). Prvi dio se sastoji od doprinosa iz LITIS, drugi je specijalnost Greyc i posljednji dio je dobro poznat oba partnera. S obzirom na taj zajednički jezik želimo podijeliti svoje stručno znanje kako bismo poboljšali najnovija dostignuća u objema zajednicama. Algoritamski dinamički grafikoni: Literatura o algoritmima za dinamičke grafove općenito počinje od aplikacija i nastoji riješiti određeni problem povezan s ovom aplikacijom. Referentni dokument u kojem su navedeni različiti konteksti nalazi se u Holmesu (2015., u općim referencama). Proučavani su različiti problemi s algoritamskog stajališta, uključujući problem komercijalnog putnika, probleme valova i više ljubaznosti. Još uvijek postoji malo doprinosa konzorcija o toj temi, ali to je samo cilj projekta. Dinamički problemi na grafikonima: Dinamički problemi sa grafovima su dvije vrste. — Oni mogu biti, s jedne strane, problemi predstavljeni u obliku dva igrača igre, kao što je problem žandarmes i lopov, gdje igra dominacije. Ovi klasični problemi imaju bogatu literaturu povezanu s nedavnim interesom za oveprobleme. Poteškoće tih problema leži u činjenici da rješenja problema moraju biti predstavljena u obliku strategije, a time i stabla odlučivanja. Meyniel je pretpostavka je jedan od glavnih izazova u teorija graf.The dva tima konzorcija imaju stručnost o tim problemima. — mogu se sastojati i od problema za koje provjera rješenja zahtijeva dinamičan, iterirani izračun. To je, na primjer, slučaj s problemima perkolacije, pomicanja čuvara (vječne dominacije) ili dominacije energije za primjene u elektroenergetskim mrežama. Na potonju temu, promotor projekta nedavno je zamoljen da napiše poglavlje knjige. (Vidjeti datoteku zahtjeva.) (Croatian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
Στη δυναμική κοινότητα γραφημάτων υπάρχουν διάφορες προσεγγίσεις για την ανάλυση κατά μέσο όρο: — αυξητική ανάλυση αλγορίθμων: μια δομή δεδομένωνδιατηρεί αναλλοίωτους στο δυναμικό γράφημα κατά τη διάρκεια της εξέλιξής του είναι η πολυπλοκότητα κατά μέσο όρο των ερωτημάτων σε αυτή τη δομή που αναλύεται — Dynamic Erdös-Rényi model: Οι Suppresions και οι προσθήκες των άκρων σχεδιάζονται τυχαία σε κάθε στάδιο του χρόνου. — περιορισμένο τυχαίο μοντέλο: η δράση της προσθήκης ή της αφαίρεσης των άκρων αποφασίζεται από έναν αντίπαλο, αλλά η τροποποιημένη κορυφογραμμή σχεδιάζεται τυχαία. Πολλές εργασίες στους αναλυτικούς συνδυασμούς υπάρχουν γύρω από τη μέση ανάλυση αλγορίθμων που λειτουργούν σε στατικά γραφήματα με επισήμανση (ή όχι). Πιο πρόσφατα, αναδύονται εργασίες για την ανάλυση γραφημάτων με περιορισμένες ετικέτες (ανάπτυξη ετικετών κατά μήκος της διαδρομής, επανάληψη ετικετών). Τυχαία γενιά: Η εξέλιξη της τεχνολογίας διαιρείται σε τρία μέρη: ad-hoc τυχαίες γεννήτριες για διαφορετικές εφαρμογές (δίκτυα κηπευτικών και τηλεπικοινωνιακά δίκτυα), πιο γενικοί αλγόριθμοι (μέθοδος Boltzmann και Monte-Carlo) και σχετικά απλοί στην προσομοίωση μοντέλων τυχαίων γραφημάτων (Erdös-Rényi, Watts-Strogatz και Barabási). Το πρώτο μέρος αποτελείται από συνεισφορές της LITIS, το δεύτερο είναι μια ειδικότητα της Greyc και το τελευταίο είναι γνωστό και στους δύο εταίρους. Δεδομένης αυτής της κοινής γλώσσας, θέλουμε να μοιραστούμε την εμπειρογνωσία μας για τη βελτίωση της τεχνολογίας και στις δύο κοινότητες. Αλγοριθμικές δυναμικές γραφικές παραστάσεις: Η βιβλιογραφία σχετικά με τους αλγορίθμους για δυναμικά γραφήματα γενικά ξεκινά από εφαρμογές και επιδιώκει να λύσει ένα συγκεκριμένο πρόβλημα που σχετίζεται με αυτή την εφαρμογή. Το έγγραφο αναφοράς που απαριθμεί τα διαφορετικά πλαίσια είναι εκείνο του Holmes (2015, στις γενικές παραπομπές). Διάφορα προβλήματα έχουν μελετηθεί από αλγοριθμική άποψη, συμπεριλαμβανομένου του προβλήματος του εμπορικού ταξιδιώτη, προβλήματα των κυμάτων, και πιο ευγένεια μονοπάτια. Υπάρχουν ακόμη λίγες συνεισφορές από την κοινοπραξία σχετικά με το θέμα, αλλά αυτός είναι μόνο ο στόχος του έργου. Δυναμικά προβλήματα στα γραφήματα: Τα δυναμικά προβλήματα με τα γραφήματα είναι δύο ειδών. — Μπορούν να είναι, αφενός, προβλήματα που παρουσιάζονται με τη μορφή παιχνιδιών δύο παικτών, όπως το πρόβλημα των χωροφυλάκων και του κλέφτη, όπου το παιχνίδι της κυριαρχίας. Αυτά τα κλασικά προβλήματα έχουν άφθονη λογοτεχνία που συνδέεται με το πρόσφατο ενδιαφέρον για αυτά τα προβλήματα. Η δυσκολία αυτών των προβλημάτων έγκειται στο γεγονός ότι οι λύσεις στο πρόβλημα πρέπει να παρουσιάζονται με τη μορφή μιας στρατηγικής, εξ ου και ενός δέντρου αποφάσεων. Η εικασία του Meyniel είναι μία από τις μεγαλύτερες προκλήσεις στη θεωρία γραφημάτων. Οι δύο ομάδες της κοινοπραξίας έχουν εμπειρογνωμοσύνη σε αυτά τα προβλήματα. — μπορούν επίσης να συνίστανται σε προβλήματα για τα οποία η επαλήθευση της λύσης απαιτεί δυναμικό και επαναλαμβανόμενο υπολογισμό. Αυτό συμβαίνει, για παράδειγμα, με τα προβλήματα της διήθησης, της μετατόπισης φρουρών (αιώνια κυριαρχία) ή της κυριαρχίας ενέργειας για εφαρμογές σε δίκτυα ηλεκτρικής ενέργειας. Σχετικά με το τελευταίο θέμα, ο φορέας υλοποίησης του έργου κλήθηκε πρόσφατα να γράψει ένα κεφάλαιο για το βιβλίο. (Βλ. φάκελο αίτησης.) (Greek) | |||||||||||||||
| Property / summary: Στη δυναμική κοινότητα γραφημάτων υπάρχουν διάφορες προσεγγίσεις για την ανάλυση κατά μέσο όρο: — αυξητική ανάλυση αλγορίθμων: μια δομή δεδομένωνδιατηρεί αναλλοίωτους στο δυναμικό γράφημα κατά τη διάρκεια της εξέλιξής του είναι η πολυπλοκότητα κατά μέσο όρο των ερωτημάτων σε αυτή τη δομή που αναλύεται — Dynamic Erdös-Rényi model: Οι Suppresions και οι προσθήκες των άκρων σχεδιάζονται τυχαία σε κάθε στάδιο του χρόνου. — περιορισμένο τυχαίο μοντέλο: η δράση της προσθήκης ή της αφαίρεσης των άκρων αποφασίζεται από έναν αντίπαλο, αλλά η τροποποιημένη κορυφογραμμή σχεδιάζεται τυχαία. Πολλές εργασίες στους αναλυτικούς συνδυασμούς υπάρχουν γύρω από τη μέση ανάλυση αλγορίθμων που λειτουργούν σε στατικά γραφήματα με επισήμανση (ή όχι). Πιο πρόσφατα, αναδύονται εργασίες για την ανάλυση γραφημάτων με περιορισμένες ετικέτες (ανάπτυξη ετικετών κατά μήκος της διαδρομής, επανάληψη ετικετών). Τυχαία γενιά: Η εξέλιξη της τεχνολογίας διαιρείται σε τρία μέρη: ad-hoc τυχαίες γεννήτριες για διαφορετικές εφαρμογές (δίκτυα κηπευτικών και τηλεπικοινωνιακά δίκτυα), πιο γενικοί αλγόριθμοι (μέθοδος Boltzmann και Monte-Carlo) και σχετικά απλοί στην προσομοίωση μοντέλων τυχαίων γραφημάτων (Erdös-Rényi, Watts-Strogatz και Barabási). Το πρώτο μέρος αποτελείται από συνεισφορές της LITIS, το δεύτερο είναι μια ειδικότητα της Greyc και το τελευταίο είναι γνωστό και στους δύο εταίρους. Δεδομένης αυτής της κοινής γλώσσας, θέλουμε να μοιραστούμε την εμπειρογνωσία μας για τη βελτίωση της τεχνολογίας και στις δύο κοινότητες. Αλγοριθμικές δυναμικές γραφικές παραστάσεις: Η βιβλιογραφία σχετικά με τους αλγορίθμους για δυναμικά γραφήματα γενικά ξεκινά από εφαρμογές και επιδιώκει να λύσει ένα συγκεκριμένο πρόβλημα που σχετίζεται με αυτή την εφαρμογή. Το έγγραφο αναφοράς που απαριθμεί τα διαφορετικά πλαίσια είναι εκείνο του Holmes (2015, στις γενικές παραπομπές). Διάφορα προβλήματα έχουν μελετηθεί από αλγοριθμική άποψη, συμπεριλαμβανομένου του προβλήματος του εμπορικού ταξιδιώτη, προβλήματα των κυμάτων, και πιο ευγένεια μονοπάτια. Υπάρχουν ακόμη λίγες συνεισφορές από την κοινοπραξία σχετικά με το θέμα, αλλά αυτός είναι μόνο ο στόχος του έργου. Δυναμικά προβλήματα στα γραφήματα: Τα δυναμικά προβλήματα με τα γραφήματα είναι δύο ειδών. — Μπορούν να είναι, αφενός, προβλήματα που παρουσιάζονται με τη μορφή παιχνιδιών δύο παικτών, όπως το πρόβλημα των χωροφυλάκων και του κλέφτη, όπου το παιχνίδι της κυριαρχίας. Αυτά τα κλασικά προβλήματα έχουν άφθονη λογοτεχνία που συνδέεται με το πρόσφατο ενδιαφέρον για αυτά τα προβλήματα. Η δυσκολία αυτών των προβλημάτων έγκειται στο γεγονός ότι οι λύσεις στο πρόβλημα πρέπει να παρουσιάζονται με τη μορφή μιας στρατηγικής, εξ ου και ενός δέντρου αποφάσεων. Η εικασία του Meyniel είναι μία από τις μεγαλύτερες προκλήσεις στη θεωρία γραφημάτων. Οι δύο ομάδες της κοινοπραξίας έχουν εμπειρογνωμοσύνη σε αυτά τα προβλήματα. — μπορούν επίσης να συνίστανται σε προβλήματα για τα οποία η επαλήθευση της λύσης απαιτεί δυναμικό και επαναλαμβανόμενο υπολογισμό. Αυτό συμβαίνει, για παράδειγμα, με τα προβλήματα της διήθησης, της μετατόπισης φρουρών (αιώνια κυριαρχία) ή της κυριαρχίας ενέργειας για εφαρμογές σε δίκτυα ηλεκτρικής ενέργειας. Σχετικά με το τελευταίο θέμα, ο φορέας υλοποίησης του έργου κλήθηκε πρόσφατα να γράψει ένα κεφάλαιο για το βιβλίο. (Βλ. φάκελο αίτησης.) (Greek) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Στη δυναμική κοινότητα γραφημάτων υπάρχουν διάφορες προσεγγίσεις για την ανάλυση κατά μέσο όρο: — αυξητική ανάλυση αλγορίθμων: μια δομή δεδομένωνδιατηρεί αναλλοίωτους στο δυναμικό γράφημα κατά τη διάρκεια της εξέλιξής του είναι η πολυπλοκότητα κατά μέσο όρο των ερωτημάτων σε αυτή τη δομή που αναλύεται — Dynamic Erdös-Rényi model: Οι Suppresions και οι προσθήκες των άκρων σχεδιάζονται τυχαία σε κάθε στάδιο του χρόνου. — περιορισμένο τυχαίο μοντέλο: η δράση της προσθήκης ή της αφαίρεσης των άκρων αποφασίζεται από έναν αντίπαλο, αλλά η τροποποιημένη κορυφογραμμή σχεδιάζεται τυχαία. Πολλές εργασίες στους αναλυτικούς συνδυασμούς υπάρχουν γύρω από τη μέση ανάλυση αλγορίθμων που λειτουργούν σε στατικά γραφήματα με επισήμανση (ή όχι). Πιο πρόσφατα, αναδύονται εργασίες για την ανάλυση γραφημάτων με περιορισμένες ετικέτες (ανάπτυξη ετικετών κατά μήκος της διαδρομής, επανάληψη ετικετών). Τυχαία γενιά: Η εξέλιξη της τεχνολογίας διαιρείται σε τρία μέρη: ad-hoc τυχαίες γεννήτριες για διαφορετικές εφαρμογές (δίκτυα κηπευτικών και τηλεπικοινωνιακά δίκτυα), πιο γενικοί αλγόριθμοι (μέθοδος Boltzmann και Monte-Carlo) και σχετικά απλοί στην προσομοίωση μοντέλων τυχαίων γραφημάτων (Erdös-Rényi, Watts-Strogatz και Barabási). Το πρώτο μέρος αποτελείται από συνεισφορές της LITIS, το δεύτερο είναι μια ειδικότητα της Greyc και το τελευταίο είναι γνωστό και στους δύο εταίρους. Δεδομένης αυτής της κοινής γλώσσας, θέλουμε να μοιραστούμε την εμπειρογνωσία μας για τη βελτίωση της τεχνολογίας και στις δύο κοινότητες. Αλγοριθμικές δυναμικές γραφικές παραστάσεις: Η βιβλιογραφία σχετικά με τους αλγορίθμους για δυναμικά γραφήματα γενικά ξεκινά από εφαρμογές και επιδιώκει να λύσει ένα συγκεκριμένο πρόβλημα που σχετίζεται με αυτή την εφαρμογή. Το έγγραφο αναφοράς που απαριθμεί τα διαφορετικά πλαίσια είναι εκείνο του Holmes (2015, στις γενικές παραπομπές). Διάφορα προβλήματα έχουν μελετηθεί από αλγοριθμική άποψη, συμπεριλαμβανομένου του προβλήματος του εμπορικού ταξιδιώτη, προβλήματα των κυμάτων, και πιο ευγένεια μονοπάτια. Υπάρχουν ακόμη λίγες συνεισφορές από την κοινοπραξία σχετικά με το θέμα, αλλά αυτός είναι μόνο ο στόχος του έργου. Δυναμικά προβλήματα στα γραφήματα: Τα δυναμικά προβλήματα με τα γραφήματα είναι δύο ειδών. — Μπορούν να είναι, αφενός, προβλήματα που παρουσιάζονται με τη μορφή παιχνιδιών δύο παικτών, όπως το πρόβλημα των χωροφυλάκων και του κλέφτη, όπου το παιχνίδι της κυριαρχίας. Αυτά τα κλασικά προβλήματα έχουν άφθονη λογοτεχνία που συνδέεται με το πρόσφατο ενδιαφέρον για αυτά τα προβλήματα. Η δυσκολία αυτών των προβλημάτων έγκειται στο γεγονός ότι οι λύσεις στο πρόβλημα πρέπει να παρουσιάζονται με τη μορφή μιας στρατηγικής, εξ ου και ενός δέντρου αποφάσεων. Η εικασία του Meyniel είναι μία από τις μεγαλύτερες προκλήσεις στη θεωρία γραφημάτων. Οι δύο ομάδες της κοινοπραξίας έχουν εμπειρογνωμοσύνη σε αυτά τα προβλήματα. — μπορούν επίσης να συνίστανται σε προβλήματα για τα οποία η επαλήθευση της λύσης απαιτεί δυναμικό και επαναλαμβανόμενο υπολογισμό. Αυτό συμβαίνει, για παράδειγμα, με τα προβλήματα της διήθησης, της μετατόπισης φρουρών (αιώνια κυριαρχία) ή της κυριαρχίας ενέργειας για εφαρμογές σε δίκτυα ηλεκτρικής ενέργειας. Σχετικά με το τελευταίο θέμα, ο φορέας υλοποίησης του έργου κλήθηκε πρόσφατα να γράψει ένα κεφάλαιο για το βιβλίο. (Βλ. φάκελο αίτησης.) (Greek) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
V komunite dynamických grafov existuje v priemere niekoľko prístupov k analýze: — analýza prírastkových algoritmov: dátová štruktúrazachováva invarianty na dynamickom grafe počas jeho vývoja je to komplexnosť v priemere dotazov na túto štruktúru, ktorá sa analyzuje – Dynamic Erdös-Rényi model: Suppresions a prírastky okrajov sú vykreslené náhodne v každom kroku času. — obmedzený náhodný model: o pridaní alebo odstránení hrán rozhoduje súper, ale upravený hrebeň je vykreslený náhodne. Veľa práce v analytických kombinátoroch existuje okolo priemernej analýzy algoritmov fungujúcich na statických grafoch označených (alebo nie). Nedávno sa pracuje na analýze grafov s obmedzenými štítkami (rozmnožovanie štítkov pozdĺž cesty, opakovanie štítkov). Náhodné generovanie: Stav techniky je rozdelený na tri časti: ad-hoc náhodné generátory pre rôzne aplikácie (viary a telekomunikačné siete), všeobecnejšie algoritmy (Boltzmann a Monte-Carlo metóda) a relatívne jednoduché simulovať modely náhodných grafov (Erdös-Rényi, Watts-Strogatz a Barabási). Prvá časť pozostáva z príspevkov z LITIS, druhá je špecializácia Greyc a posledná časť je dobre známa obom partnerom. Vzhľadom na tento spoločný jazyk sa chceme podeliť o naše odborné znalosti s cieľom zlepšiť stav techniky v oboch komunitách. Algoritmické dynamické grafy: Literatúra o algoritmoch dynamických grafov vo všeobecnosti začína od aplikácií a snaží sa vyriešiť konkrétny problém súvisiaci s touto aplikáciou. Referenčný dokument, v ktorom sa uvádzajú rôzne súvislosti, je dokument Holmes (2015, vo všeobecných odkazoch). Z algoritmického hľadiska sa skúmali rôzne problémy vrátane problému komerčného cestujúceho, problémov s vlnami a zdvorilejších ciest. Na túto tému je stále málo príspevkov konzorcia, ale to je len cieľ projektu. Dynamické problémy na grafoch: Dynamické problémy s grafmi sú dvoch druhov. — Môžu byť, na jednej strane, problémy prezentované vo forme dvojhrových hier, ako je problém žandárov a zlodeja, kde hra nadvlády. Tieto klasické problémy majú bohatú literatúru spojenú s nedávnym záujmom o tieto problémy. Ťažkosti týchto problémov spočívajú v tom, že riešenia tohto problému musia byť prezentované vo forme stratégie, teda v podobe rozhodovacieho stromu. Meynielova domnienka je jednou z hlavných výziev v teórii grafu. Dva tímy konzorcia majú odborné znalosti o týchto problémoch. — môžu pozostávať aj z problémov, pri ktorých si overenie riešenia vyžaduje dynamický, iterovaný výpočet. Je to tak napríklad v prípade problémov s perkoláciou, posunom strážcov (večná nadvláda) alebo prevahou moci pre aplikácie do elektrických rozvodných sietí. Pokiaľ ide o druhú tému, organizátor projektu bol nedávno požiadaný, aby napísal kapitolu knihy. (Pozri súbor žiadosti.) (Slovak) | |||||||||||||||
| Property / summary: V komunite dynamických grafov existuje v priemere niekoľko prístupov k analýze: — analýza prírastkových algoritmov: dátová štruktúrazachováva invarianty na dynamickom grafe počas jeho vývoja je to komplexnosť v priemere dotazov na túto štruktúru, ktorá sa analyzuje – Dynamic Erdös-Rényi model: Suppresions a prírastky okrajov sú vykreslené náhodne v každom kroku času. — obmedzený náhodný model: o pridaní alebo odstránení hrán rozhoduje súper, ale upravený hrebeň je vykreslený náhodne. Veľa práce v analytických kombinátoroch existuje okolo priemernej analýzy algoritmov fungujúcich na statických grafoch označených (alebo nie). Nedávno sa pracuje na analýze grafov s obmedzenými štítkami (rozmnožovanie štítkov pozdĺž cesty, opakovanie štítkov). Náhodné generovanie: Stav techniky je rozdelený na tri časti: ad-hoc náhodné generátory pre rôzne aplikácie (viary a telekomunikačné siete), všeobecnejšie algoritmy (Boltzmann a Monte-Carlo metóda) a relatívne jednoduché simulovať modely náhodných grafov (Erdös-Rényi, Watts-Strogatz a Barabási). Prvá časť pozostáva z príspevkov z LITIS, druhá je špecializácia Greyc a posledná časť je dobre známa obom partnerom. Vzhľadom na tento spoločný jazyk sa chceme podeliť o naše odborné znalosti s cieľom zlepšiť stav techniky v oboch komunitách. Algoritmické dynamické grafy: Literatúra o algoritmoch dynamických grafov vo všeobecnosti začína od aplikácií a snaží sa vyriešiť konkrétny problém súvisiaci s touto aplikáciou. Referenčný dokument, v ktorom sa uvádzajú rôzne súvislosti, je dokument Holmes (2015, vo všeobecných odkazoch). Z algoritmického hľadiska sa skúmali rôzne problémy vrátane problému komerčného cestujúceho, problémov s vlnami a zdvorilejších ciest. Na túto tému je stále málo príspevkov konzorcia, ale to je len cieľ projektu. Dynamické problémy na grafoch: Dynamické problémy s grafmi sú dvoch druhov. — Môžu byť, na jednej strane, problémy prezentované vo forme dvojhrových hier, ako je problém žandárov a zlodeja, kde hra nadvlády. Tieto klasické problémy majú bohatú literatúru spojenú s nedávnym záujmom o tieto problémy. Ťažkosti týchto problémov spočívajú v tom, že riešenia tohto problému musia byť prezentované vo forme stratégie, teda v podobe rozhodovacieho stromu. Meynielova domnienka je jednou z hlavných výziev v teórii grafu. Dva tímy konzorcia majú odborné znalosti o týchto problémoch. — môžu pozostávať aj z problémov, pri ktorých si overenie riešenia vyžaduje dynamický, iterovaný výpočet. Je to tak napríklad v prípade problémov s perkoláciou, posunom strážcov (večná nadvláda) alebo prevahou moci pre aplikácie do elektrických rozvodných sietí. Pokiaľ ide o druhú tému, organizátor projektu bol nedávno požiadaný, aby napísal kapitolu knihy. (Pozri súbor žiadosti.) (Slovak) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: V komunite dynamických grafov existuje v priemere niekoľko prístupov k analýze: — analýza prírastkových algoritmov: dátová štruktúrazachováva invarianty na dynamickom grafe počas jeho vývoja je to komplexnosť v priemere dotazov na túto štruktúru, ktorá sa analyzuje – Dynamic Erdös-Rényi model: Suppresions a prírastky okrajov sú vykreslené náhodne v každom kroku času. — obmedzený náhodný model: o pridaní alebo odstránení hrán rozhoduje súper, ale upravený hrebeň je vykreslený náhodne. Veľa práce v analytických kombinátoroch existuje okolo priemernej analýzy algoritmov fungujúcich na statických grafoch označených (alebo nie). Nedávno sa pracuje na analýze grafov s obmedzenými štítkami (rozmnožovanie štítkov pozdĺž cesty, opakovanie štítkov). Náhodné generovanie: Stav techniky je rozdelený na tri časti: ad-hoc náhodné generátory pre rôzne aplikácie (viary a telekomunikačné siete), všeobecnejšie algoritmy (Boltzmann a Monte-Carlo metóda) a relatívne jednoduché simulovať modely náhodných grafov (Erdös-Rényi, Watts-Strogatz a Barabási). Prvá časť pozostáva z príspevkov z LITIS, druhá je špecializácia Greyc a posledná časť je dobre známa obom partnerom. Vzhľadom na tento spoločný jazyk sa chceme podeliť o naše odborné znalosti s cieľom zlepšiť stav techniky v oboch komunitách. Algoritmické dynamické grafy: Literatúra o algoritmoch dynamických grafov vo všeobecnosti začína od aplikácií a snaží sa vyriešiť konkrétny problém súvisiaci s touto aplikáciou. Referenčný dokument, v ktorom sa uvádzajú rôzne súvislosti, je dokument Holmes (2015, vo všeobecných odkazoch). Z algoritmického hľadiska sa skúmali rôzne problémy vrátane problému komerčného cestujúceho, problémov s vlnami a zdvorilejších ciest. Na túto tému je stále málo príspevkov konzorcia, ale to je len cieľ projektu. Dynamické problémy na grafoch: Dynamické problémy s grafmi sú dvoch druhov. — Môžu byť, na jednej strane, problémy prezentované vo forme dvojhrových hier, ako je problém žandárov a zlodeja, kde hra nadvlády. Tieto klasické problémy majú bohatú literatúru spojenú s nedávnym záujmom o tieto problémy. Ťažkosti týchto problémov spočívajú v tom, že riešenia tohto problému musia byť prezentované vo forme stratégie, teda v podobe rozhodovacieho stromu. Meynielova domnienka je jednou z hlavných výziev v teórii grafu. Dva tímy konzorcia majú odborné znalosti o týchto problémoch. — môžu pozostávať aj z problémov, pri ktorých si overenie riešenia vyžaduje dynamický, iterovaný výpočet. Je to tak napríklad v prípade problémov s perkoláciou, posunom strážcov (večná nadvláda) alebo prevahou moci pre aplikácie do elektrických rozvodných sietí. Pokiaľ ide o druhú tému, organizátor projektu bol nedávno požiadaný, aby napísal kapitolu knihy. (Pozri súbor žiadosti.) (Slovak) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
Dynaamisessa kaavioyhteisössä on useita lähestymistapoja analyysiin keskimäärin: — asteittainen algoritmianalyysi: tietorakenne ylläpitää invariantteja dynaamisessa kaaviossa sen evoluution aikana, se on tämän rakenteen kyselyiden keskimäärin monimutkaisuus, joka analysoidaan – Dynamic Erdös-Rényi -malli: Suppresions ja lisäykset reunat piirretään satunnaisesti kussakin vaiheessa aikaa. — rajoitettu satunnainen malli: vastustaja päättää reunojen lisäämisestä tai poistamisesta, mutta muokattu harjanteen piirretään satunnaisesti. Monet työt analyyttisten combinatorials on noin keskimääräinen analyysi algoritmeja toimivat staattisia kaavioita merkitty (tai ei). Viime aikoina on kehittymässä grafiikka-analyysejä, joissa on rajoitettuja merkintöjä (etikettien kasvu matkan varrella, tarrojen toistaminen). Satunnainen sukupolvi: Uusinta tekniikkaa on jaettu kolmeen osaan: satunnaiset satunnaisgeneraattorit eri sovelluksiin (viaariverkot ja televiestintäverkot), yleisempiä algoritmeja (Boltzmannin ja Monte-Carlon menetelmä) ja suhteellisen yksinkertaisia simuloida satunnaisia kaaviomalleja (Erdös-Rényi, Watts-Strogatz ja Barabási). Ensimmäinen osa koostuu LITIS:n maksuosuuksista, toinen on Greycin erikoisuus ja viimeinen osa on hyvin molempien osapuolten tiedossa. Tämän yhteisen kielen vuoksi haluamme jakaa asiantuntemustamme molempien yhteisöjen huipputason parantamiseksi. Algoritmidynaamiset kaaviot: Dynaamisten kaavioiden algoritmeja koskeva kirjallisuus alkaa yleensä sovelluksista ja pyrkii ratkaisemaan tähän sovellukseen liittyvän erityisongelman. Viiteasiakirja, jossa luetellaan eri asiayhteydet, on Holmesin viiteasiakirja (2015, yleisissä viittauksissa). Algoritmista näkökulmasta on tutkittu erilaisia ongelmia, kuten kaupallisen matkustajan ongelma, aaltojen ongelmat ja kohteliaisuuspolut. Konsortiolta on vielä vain vähän asiaa koskevia kannanottoja, mutta tämä on vain hankkeen tavoite. Dynaamiset ongelmat kaavioissa: Dynaamiset ongelmat kaavioissa ovat kahdenlaisia. — Ne voivat olla, toisaalta, ongelmia esitetään muodossa kahden pelaajan pelejä, kuten ongelma santarmit ja varas, jossa peli dominaatio. Nämä klassiset ongelmat ovat runsaasti kirjallisuutta, joka liittyy viimeaikaiseen kiinnostukseen näitä ongelmia kohtaan. Näiden ongelmien vaikeus on se, että ongelman ratkaisut on esitettävä strategiana, eli päätöksentekopuuna. Meyniel arveluihin on yksi suurimmista haasteista kaavioteoria.Kahdella joukkueella on asiantuntemusta näistä ongelmista. — ne voivat muodostua myös ongelmista, joiden osalta ratkaisun todentaminen edellyttää dynaamista, itioitua laskentaa. Tämä koskee esimerkiksi suojusta, suojusten vaihtamista (ikuinen ylivalta) tai sähköverkkoihin liittyvien sovellusten virranhallintaa. Jälkimmäisen aiheen osalta hankkeen toteuttajaa pyydettiin äskettäin kirjoittamaan kirjan luku. (Ks. hakemustiedosto.) (Finnish) | |||||||||||||||
| Property / summary: Dynaamisessa kaavioyhteisössä on useita lähestymistapoja analyysiin keskimäärin: — asteittainen algoritmianalyysi: tietorakenne ylläpitää invariantteja dynaamisessa kaaviossa sen evoluution aikana, se on tämän rakenteen kyselyiden keskimäärin monimutkaisuus, joka analysoidaan – Dynamic Erdös-Rényi -malli: Suppresions ja lisäykset reunat piirretään satunnaisesti kussakin vaiheessa aikaa. — rajoitettu satunnainen malli: vastustaja päättää reunojen lisäämisestä tai poistamisesta, mutta muokattu harjanteen piirretään satunnaisesti. Monet työt analyyttisten combinatorials on noin keskimääräinen analyysi algoritmeja toimivat staattisia kaavioita merkitty (tai ei). Viime aikoina on kehittymässä grafiikka-analyysejä, joissa on rajoitettuja merkintöjä (etikettien kasvu matkan varrella, tarrojen toistaminen). Satunnainen sukupolvi: Uusinta tekniikkaa on jaettu kolmeen osaan: satunnaiset satunnaisgeneraattorit eri sovelluksiin (viaariverkot ja televiestintäverkot), yleisempiä algoritmeja (Boltzmannin ja Monte-Carlon menetelmä) ja suhteellisen yksinkertaisia simuloida satunnaisia kaaviomalleja (Erdös-Rényi, Watts-Strogatz ja Barabási). Ensimmäinen osa koostuu LITIS:n maksuosuuksista, toinen on Greycin erikoisuus ja viimeinen osa on hyvin molempien osapuolten tiedossa. Tämän yhteisen kielen vuoksi haluamme jakaa asiantuntemustamme molempien yhteisöjen huipputason parantamiseksi. Algoritmidynaamiset kaaviot: Dynaamisten kaavioiden algoritmeja koskeva kirjallisuus alkaa yleensä sovelluksista ja pyrkii ratkaisemaan tähän sovellukseen liittyvän erityisongelman. Viiteasiakirja, jossa luetellaan eri asiayhteydet, on Holmesin viiteasiakirja (2015, yleisissä viittauksissa). Algoritmista näkökulmasta on tutkittu erilaisia ongelmia, kuten kaupallisen matkustajan ongelma, aaltojen ongelmat ja kohteliaisuuspolut. Konsortiolta on vielä vain vähän asiaa koskevia kannanottoja, mutta tämä on vain hankkeen tavoite. Dynaamiset ongelmat kaavioissa: Dynaamiset ongelmat kaavioissa ovat kahdenlaisia. — Ne voivat olla, toisaalta, ongelmia esitetään muodossa kahden pelaajan pelejä, kuten ongelma santarmit ja varas, jossa peli dominaatio. Nämä klassiset ongelmat ovat runsaasti kirjallisuutta, joka liittyy viimeaikaiseen kiinnostukseen näitä ongelmia kohtaan. Näiden ongelmien vaikeus on se, että ongelman ratkaisut on esitettävä strategiana, eli päätöksentekopuuna. Meyniel arveluihin on yksi suurimmista haasteista kaavioteoria.Kahdella joukkueella on asiantuntemusta näistä ongelmista. — ne voivat muodostua myös ongelmista, joiden osalta ratkaisun todentaminen edellyttää dynaamista, itioitua laskentaa. Tämä koskee esimerkiksi suojusta, suojusten vaihtamista (ikuinen ylivalta) tai sähköverkkoihin liittyvien sovellusten virranhallintaa. Jälkimmäisen aiheen osalta hankkeen toteuttajaa pyydettiin äskettäin kirjoittamaan kirjan luku. (Ks. hakemustiedosto.) (Finnish) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Dynaamisessa kaavioyhteisössä on useita lähestymistapoja analyysiin keskimäärin: — asteittainen algoritmianalyysi: tietorakenne ylläpitää invariantteja dynaamisessa kaaviossa sen evoluution aikana, se on tämän rakenteen kyselyiden keskimäärin monimutkaisuus, joka analysoidaan – Dynamic Erdös-Rényi -malli: Suppresions ja lisäykset reunat piirretään satunnaisesti kussakin vaiheessa aikaa. — rajoitettu satunnainen malli: vastustaja päättää reunojen lisäämisestä tai poistamisesta, mutta muokattu harjanteen piirretään satunnaisesti. Monet työt analyyttisten combinatorials on noin keskimääräinen analyysi algoritmeja toimivat staattisia kaavioita merkitty (tai ei). Viime aikoina on kehittymässä grafiikka-analyysejä, joissa on rajoitettuja merkintöjä (etikettien kasvu matkan varrella, tarrojen toistaminen). Satunnainen sukupolvi: Uusinta tekniikkaa on jaettu kolmeen osaan: satunnaiset satunnaisgeneraattorit eri sovelluksiin (viaariverkot ja televiestintäverkot), yleisempiä algoritmeja (Boltzmannin ja Monte-Carlon menetelmä) ja suhteellisen yksinkertaisia simuloida satunnaisia kaaviomalleja (Erdös-Rényi, Watts-Strogatz ja Barabási). Ensimmäinen osa koostuu LITIS:n maksuosuuksista, toinen on Greycin erikoisuus ja viimeinen osa on hyvin molempien osapuolten tiedossa. Tämän yhteisen kielen vuoksi haluamme jakaa asiantuntemustamme molempien yhteisöjen huipputason parantamiseksi. Algoritmidynaamiset kaaviot: Dynaamisten kaavioiden algoritmeja koskeva kirjallisuus alkaa yleensä sovelluksista ja pyrkii ratkaisemaan tähän sovellukseen liittyvän erityisongelman. Viiteasiakirja, jossa luetellaan eri asiayhteydet, on Holmesin viiteasiakirja (2015, yleisissä viittauksissa). Algoritmista näkökulmasta on tutkittu erilaisia ongelmia, kuten kaupallisen matkustajan ongelma, aaltojen ongelmat ja kohteliaisuuspolut. Konsortiolta on vielä vain vähän asiaa koskevia kannanottoja, mutta tämä on vain hankkeen tavoite. Dynaamiset ongelmat kaavioissa: Dynaamiset ongelmat kaavioissa ovat kahdenlaisia. — Ne voivat olla, toisaalta, ongelmia esitetään muodossa kahden pelaajan pelejä, kuten ongelma santarmit ja varas, jossa peli dominaatio. Nämä klassiset ongelmat ovat runsaasti kirjallisuutta, joka liittyy viimeaikaiseen kiinnostukseen näitä ongelmia kohtaan. Näiden ongelmien vaikeus on se, että ongelman ratkaisut on esitettävä strategiana, eli päätöksentekopuuna. Meyniel arveluihin on yksi suurimmista haasteista kaavioteoria.Kahdella joukkueella on asiantuntemusta näistä ongelmista. — ne voivat muodostua myös ongelmista, joiden osalta ratkaisun todentaminen edellyttää dynaamista, itioitua laskentaa. Tämä koskee esimerkiksi suojusta, suojusten vaihtamista (ikuinen ylivalta) tai sähköverkkoihin liittyvien sovellusten virranhallintaa. Jälkimmäisen aiheen osalta hankkeen toteuttajaa pyydettiin äskettäin kirjoittamaan kirjan luku. (Ks. hakemustiedosto.) (Finnish) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
W środowisku dynamicznych wykresów istnieje średnio kilka podejść do analizy: — przyrostowa analiza algorytmów: struktura danych utrzymuje niezmienność na wykresie dynamicznym podczas jego ewolucji, jest to skomplikowanie średnio zapytań do tej struktury, która jest analizowana – model Dynamic Erdös-Rényi: Supresje i dodatki krawędzi są rysowane losowo na każdym kroku czasu. — ograniczony model losowy: o akcji dodawania lub usuwania krawędzi decyduje przeciwnik, ale zmodyfikowany grzbiet jest losowo rysowany. Wiele prac w kombinatorach analitycznych istnieje wokół średniej analizy algorytmów działających na wykresach statycznych oznakowanych (lub nie). Ostatnio pojawiają się prace nad analizą wykresów z ograniczonymi etykietami (wzrost etykiet po drodze, powtarzanie etykiet). Generowanie losowe: Stan techniki dzieli się na trzy części: generatory losowe ad hoc do różnych zastosowań (sieci voary i sieci telekomunikacyjne), bardziej ogólne algorytmy (metoda Boltzmann i Monte-Carlo) oraz stosunkowo proste do symulacji losowych modeli wykresów (Erdös-Rényi, Watts-Strogatz i Barabási). Pierwsza część składa się z wkładów LITIS, druga to specjalność Greyc, a ostatnia część jest dobrze znana obu partnerom. Biorąc pod uwagę ten wspólny język, chcemy dzielić się naszą wiedzą fachową w celu poprawy stanu techniki w obu społecznościach. Algorytmiczne wykresy dynamiczne: Literatura na temat algorytmów wykresów dynamicznych zazwyczaj zaczyna się od aplikacji i ma na celu rozwiązanie konkretnego problemu związanego z tą aplikacją. Dokument referencyjny, w którym wymieniono różne konteksty, dotyczy Holmesa (2015 r., w odniesieniach ogólnych). Z algorytmicznego punktu widzenia przeanalizowano różne problemy, w tym problem podróżnika komercyjnego, problemy fal i bardziej uprzejmości. Konsorcjum wciąż ma niewiele wkładów na ten temat, ale jest to tylko cel projektu. Dynamiczne problemy na wykresach: Dynamiczne problemy z wykresami są dwa rodzaje. — Mogą to być, z jednej strony, problemy prezentowane w postaci gier dla dwóch graczy, takich jak problem żandarmów i złodzieja, gdzie gra dominacji. Te klasyczne problemy mają obszerną literaturę związaną z niedawnym zainteresowaniem tymi problemami. Trudność tych problemów polega na tym, że rozwiązania problemu muszą być przedstawione w formie strategii, a zatem schematu decyzyjnego. Przypuszczenie Meyniela jest jednym z głównych wyzwań w teorii wykresów. Oba zespoły konsorcjum mają wiedzę na temat tych problemów. — mogą one również składać się z problemów, w przypadku których weryfikacja rozwiązania wymaga dynamicznego, wieloetapowego obliczenia. Dzieje się tak na przykład w przypadku problemów perkolacji, przesuwania osłon (wieczna dominacja) lub dominacji mocy dla zastosowań w sieciach energetycznych. Na ten ostatni temat promotor projektu został niedawno poproszony o napisanie rozdziału książki. (Patrz plik wniosku.) (Polish) | |||||||||||||||
| Property / summary: W środowisku dynamicznych wykresów istnieje średnio kilka podejść do analizy: — przyrostowa analiza algorytmów: struktura danych utrzymuje niezmienność na wykresie dynamicznym podczas jego ewolucji, jest to skomplikowanie średnio zapytań do tej struktury, która jest analizowana – model Dynamic Erdös-Rényi: Supresje i dodatki krawędzi są rysowane losowo na każdym kroku czasu. — ograniczony model losowy: o akcji dodawania lub usuwania krawędzi decyduje przeciwnik, ale zmodyfikowany grzbiet jest losowo rysowany. Wiele prac w kombinatorach analitycznych istnieje wokół średniej analizy algorytmów działających na wykresach statycznych oznakowanych (lub nie). Ostatnio pojawiają się prace nad analizą wykresów z ograniczonymi etykietami (wzrost etykiet po drodze, powtarzanie etykiet). Generowanie losowe: Stan techniki dzieli się na trzy części: generatory losowe ad hoc do różnych zastosowań (sieci voary i sieci telekomunikacyjne), bardziej ogólne algorytmy (metoda Boltzmann i Monte-Carlo) oraz stosunkowo proste do symulacji losowych modeli wykresów (Erdös-Rényi, Watts-Strogatz i Barabási). Pierwsza część składa się z wkładów LITIS, druga to specjalność Greyc, a ostatnia część jest dobrze znana obu partnerom. Biorąc pod uwagę ten wspólny język, chcemy dzielić się naszą wiedzą fachową w celu poprawy stanu techniki w obu społecznościach. Algorytmiczne wykresy dynamiczne: Literatura na temat algorytmów wykresów dynamicznych zazwyczaj zaczyna się od aplikacji i ma na celu rozwiązanie konkretnego problemu związanego z tą aplikacją. Dokument referencyjny, w którym wymieniono różne konteksty, dotyczy Holmesa (2015 r., w odniesieniach ogólnych). Z algorytmicznego punktu widzenia przeanalizowano różne problemy, w tym problem podróżnika komercyjnego, problemy fal i bardziej uprzejmości. Konsorcjum wciąż ma niewiele wkładów na ten temat, ale jest to tylko cel projektu. Dynamiczne problemy na wykresach: Dynamiczne problemy z wykresami są dwa rodzaje. — Mogą to być, z jednej strony, problemy prezentowane w postaci gier dla dwóch graczy, takich jak problem żandarmów i złodzieja, gdzie gra dominacji. Te klasyczne problemy mają obszerną literaturę związaną z niedawnym zainteresowaniem tymi problemami. Trudność tych problemów polega na tym, że rozwiązania problemu muszą być przedstawione w formie strategii, a zatem schematu decyzyjnego. Przypuszczenie Meyniela jest jednym z głównych wyzwań w teorii wykresów. Oba zespoły konsorcjum mają wiedzę na temat tych problemów. — mogą one również składać się z problemów, w przypadku których weryfikacja rozwiązania wymaga dynamicznego, wieloetapowego obliczenia. Dzieje się tak na przykład w przypadku problemów perkolacji, przesuwania osłon (wieczna dominacja) lub dominacji mocy dla zastosowań w sieciach energetycznych. Na ten ostatni temat promotor projektu został niedawno poproszony o napisanie rozdziału książki. (Patrz plik wniosku.) (Polish) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: W środowisku dynamicznych wykresów istnieje średnio kilka podejść do analizy: — przyrostowa analiza algorytmów: struktura danych utrzymuje niezmienność na wykresie dynamicznym podczas jego ewolucji, jest to skomplikowanie średnio zapytań do tej struktury, która jest analizowana – model Dynamic Erdös-Rényi: Supresje i dodatki krawędzi są rysowane losowo na każdym kroku czasu. — ograniczony model losowy: o akcji dodawania lub usuwania krawędzi decyduje przeciwnik, ale zmodyfikowany grzbiet jest losowo rysowany. Wiele prac w kombinatorach analitycznych istnieje wokół średniej analizy algorytmów działających na wykresach statycznych oznakowanych (lub nie). Ostatnio pojawiają się prace nad analizą wykresów z ograniczonymi etykietami (wzrost etykiet po drodze, powtarzanie etykiet). Generowanie losowe: Stan techniki dzieli się na trzy części: generatory losowe ad hoc do różnych zastosowań (sieci voary i sieci telekomunikacyjne), bardziej ogólne algorytmy (metoda Boltzmann i Monte-Carlo) oraz stosunkowo proste do symulacji losowych modeli wykresów (Erdös-Rényi, Watts-Strogatz i Barabási). Pierwsza część składa się z wkładów LITIS, druga to specjalność Greyc, a ostatnia część jest dobrze znana obu partnerom. Biorąc pod uwagę ten wspólny język, chcemy dzielić się naszą wiedzą fachową w celu poprawy stanu techniki w obu społecznościach. Algorytmiczne wykresy dynamiczne: Literatura na temat algorytmów wykresów dynamicznych zazwyczaj zaczyna się od aplikacji i ma na celu rozwiązanie konkretnego problemu związanego z tą aplikacją. Dokument referencyjny, w którym wymieniono różne konteksty, dotyczy Holmesa (2015 r., w odniesieniach ogólnych). Z algorytmicznego punktu widzenia przeanalizowano różne problemy, w tym problem podróżnika komercyjnego, problemy fal i bardziej uprzejmości. Konsorcjum wciąż ma niewiele wkładów na ten temat, ale jest to tylko cel projektu. Dynamiczne problemy na wykresach: Dynamiczne problemy z wykresami są dwa rodzaje. — Mogą to być, z jednej strony, problemy prezentowane w postaci gier dla dwóch graczy, takich jak problem żandarmów i złodzieja, gdzie gra dominacji. Te klasyczne problemy mają obszerną literaturę związaną z niedawnym zainteresowaniem tymi problemami. Trudność tych problemów polega na tym, że rozwiązania problemu muszą być przedstawione w formie strategii, a zatem schematu decyzyjnego. Przypuszczenie Meyniela jest jednym z głównych wyzwań w teorii wykresów. Oba zespoły konsorcjum mają wiedzę na temat tych problemów. — mogą one również składać się z problemów, w przypadku których weryfikacja rozwiązania wymaga dynamicznego, wieloetapowego obliczenia. Dzieje się tak na przykład w przypadku problemów perkolacji, przesuwania osłon (wieczna dominacja) lub dominacji mocy dla zastosowań w sieciach energetycznych. Na ten ostatni temat promotor projektu został niedawno poproszony o napisanie rozdziału książki. (Patrz plik wniosku.) (Polish) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
A dinamikus gráfok közösségében átlagosan több megközelítés létezik: – növekményes algoritmuselemzés: az adatstruktúra evolúciója során invariánsokat tart fenn a dinamikus gráfon, átlagosan az elemzett struktúrára vonatkozó lekérdezések összetettsége – Dynamic Erdös-Rényi modell: A készleteket és az élek hozzáadását véletlenszerűen kell rajzolni az idő minden egyes lépésénél. – korlátozott véletlenszerű modell: az élek hozzáadásának vagy eltávolításának műveletét az ellenfél dönti el, de a módosított gerincet véletlenszerűen rajzolják. Analitikus kombinációkban sok munka létezik a statikus gráfokon (vagy nem) jelölt (vagy nem) grafikákon működő algoritmusok átlagelemzése körül. A közelmúltban a gráfelemzéssel kapcsolatos munka korlátozott címkékkel (a címkék növekedése útközben, a címkék megismétlése) kapcsolatos munka alakul ki. Véletlenszerű generáció: A technika állása három részre oszlik: ad-hoc véletlenszerű generátorok különböző alkalmazásokhoz (viárius hálózatok és távközlési hálózatok), általánosabb algoritmusok (Boltzmann és Monte-Carlo módszer) és viszonylag egyszerű szimulálni véletlenszerű gráfmodelleket (Erdös-Rényi, Watts-Strogatz és Barabási). Az első rész a LITIS hozzájárulásaiból áll, a második Greyc specialitása, az utolsó rész pedig mindkét fél számára jól ismert. Tekintettel erre a közös nyelvre, szeretnénk megosztani szakértelmünket annak érdekében, hogy mindkét közösség korszerűbbé váljon. Algoritmikus dinamikus gráfok: A dinamikus gráfok algoritmusairól szóló szakirodalom általában alkalmazásokból indul ki, és az alkalmazással kapcsolatos konkrét probléma megoldására törekszik. A különböző összefüggéseket felsoroló referenciadokumentum Holmesé (2015, az általános hivatkozásokban). Különböző problémákat vizsgáltunk algoritmikus szempontból, beleértve a kereskedelmi utazó problémáját, a hullámok problémáit és az udvariasabb utakat. Még mindig kevés a konzorcium hozzájárulása a témában, de ez csak a projekt célja. Dinamikus problémák a grafikonokon: A gráfokkal kapcsolatos dinamikus problémák kétféleek. – Ezek lehetnek, egyrészt a problémák bemutatott formájában kétjátékos játékok, mint például a probléma a csendőrség és a tolvaj, ahol a játék az uralom. Ezeknek a klasszikus problémáknak bőséges szakirodaloma van, ami az utóbbi időben e problémák iránti érdeklődéshez kapcsolódik. E problémák nehézsége abban rejlik, hogy a probléma megoldását stratégiában, azaz döntési fában kell bemutatni. Meyniel sejtése az egyik legnagyobb kihívás a grafikonelméletben.A konzorcium két csapata szakértelemmel rendelkezik ezekkel a problémákkal kapcsolatban. – olyan problémák is lehetnek, amelyek esetében a megoldás ellenőrzése dinamikus, iterált számítást igényel. Ez a helyzet például a perkoláció, a védőburkolatok elmozdítása (örök dominancia) vagy az erőátviteli rendszer alkalmazásai esetében. Az utóbbi témában a projektgazdát a közelmúltban felkérték, hogy írjon könyvfejezetet. (Lásd a kérelemfájlt.) (Hungarian) | |||||||||||||||
| Property / summary: A dinamikus gráfok közösségében átlagosan több megközelítés létezik: – növekményes algoritmuselemzés: az adatstruktúra evolúciója során invariánsokat tart fenn a dinamikus gráfon, átlagosan az elemzett struktúrára vonatkozó lekérdezések összetettsége – Dynamic Erdös-Rényi modell: A készleteket és az élek hozzáadását véletlenszerűen kell rajzolni az idő minden egyes lépésénél. – korlátozott véletlenszerű modell: az élek hozzáadásának vagy eltávolításának műveletét az ellenfél dönti el, de a módosított gerincet véletlenszerűen rajzolják. Analitikus kombinációkban sok munka létezik a statikus gráfokon (vagy nem) jelölt (vagy nem) grafikákon működő algoritmusok átlagelemzése körül. A közelmúltban a gráfelemzéssel kapcsolatos munka korlátozott címkékkel (a címkék növekedése útközben, a címkék megismétlése) kapcsolatos munka alakul ki. Véletlenszerű generáció: A technika állása három részre oszlik: ad-hoc véletlenszerű generátorok különböző alkalmazásokhoz (viárius hálózatok és távközlési hálózatok), általánosabb algoritmusok (Boltzmann és Monte-Carlo módszer) és viszonylag egyszerű szimulálni véletlenszerű gráfmodelleket (Erdös-Rényi, Watts-Strogatz és Barabási). Az első rész a LITIS hozzájárulásaiból áll, a második Greyc specialitása, az utolsó rész pedig mindkét fél számára jól ismert. Tekintettel erre a közös nyelvre, szeretnénk megosztani szakértelmünket annak érdekében, hogy mindkét közösség korszerűbbé váljon. Algoritmikus dinamikus gráfok: A dinamikus gráfok algoritmusairól szóló szakirodalom általában alkalmazásokból indul ki, és az alkalmazással kapcsolatos konkrét probléma megoldására törekszik. A különböző összefüggéseket felsoroló referenciadokumentum Holmesé (2015, az általános hivatkozásokban). Különböző problémákat vizsgáltunk algoritmikus szempontból, beleértve a kereskedelmi utazó problémáját, a hullámok problémáit és az udvariasabb utakat. Még mindig kevés a konzorcium hozzájárulása a témában, de ez csak a projekt célja. Dinamikus problémák a grafikonokon: A gráfokkal kapcsolatos dinamikus problémák kétféleek. – Ezek lehetnek, egyrészt a problémák bemutatott formájában kétjátékos játékok, mint például a probléma a csendőrség és a tolvaj, ahol a játék az uralom. Ezeknek a klasszikus problémáknak bőséges szakirodaloma van, ami az utóbbi időben e problémák iránti érdeklődéshez kapcsolódik. E problémák nehézsége abban rejlik, hogy a probléma megoldását stratégiában, azaz döntési fában kell bemutatni. Meyniel sejtése az egyik legnagyobb kihívás a grafikonelméletben.A konzorcium két csapata szakértelemmel rendelkezik ezekkel a problémákkal kapcsolatban. – olyan problémák is lehetnek, amelyek esetében a megoldás ellenőrzése dinamikus, iterált számítást igényel. Ez a helyzet például a perkoláció, a védőburkolatok elmozdítása (örök dominancia) vagy az erőátviteli rendszer alkalmazásai esetében. Az utóbbi témában a projektgazdát a közelmúltban felkérték, hogy írjon könyvfejezetet. (Lásd a kérelemfájlt.) (Hungarian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: A dinamikus gráfok közösségében átlagosan több megközelítés létezik: – növekményes algoritmuselemzés: az adatstruktúra evolúciója során invariánsokat tart fenn a dinamikus gráfon, átlagosan az elemzett struktúrára vonatkozó lekérdezések összetettsége – Dynamic Erdös-Rényi modell: A készleteket és az élek hozzáadását véletlenszerűen kell rajzolni az idő minden egyes lépésénél. – korlátozott véletlenszerű modell: az élek hozzáadásának vagy eltávolításának műveletét az ellenfél dönti el, de a módosított gerincet véletlenszerűen rajzolják. Analitikus kombinációkban sok munka létezik a statikus gráfokon (vagy nem) jelölt (vagy nem) grafikákon működő algoritmusok átlagelemzése körül. A közelmúltban a gráfelemzéssel kapcsolatos munka korlátozott címkékkel (a címkék növekedése útközben, a címkék megismétlése) kapcsolatos munka alakul ki. Véletlenszerű generáció: A technika állása három részre oszlik: ad-hoc véletlenszerű generátorok különböző alkalmazásokhoz (viárius hálózatok és távközlési hálózatok), általánosabb algoritmusok (Boltzmann és Monte-Carlo módszer) és viszonylag egyszerű szimulálni véletlenszerű gráfmodelleket (Erdös-Rényi, Watts-Strogatz és Barabási). Az első rész a LITIS hozzájárulásaiból áll, a második Greyc specialitása, az utolsó rész pedig mindkét fél számára jól ismert. Tekintettel erre a közös nyelvre, szeretnénk megosztani szakértelmünket annak érdekében, hogy mindkét közösség korszerűbbé váljon. Algoritmikus dinamikus gráfok: A dinamikus gráfok algoritmusairól szóló szakirodalom általában alkalmazásokból indul ki, és az alkalmazással kapcsolatos konkrét probléma megoldására törekszik. A különböző összefüggéseket felsoroló referenciadokumentum Holmesé (2015, az általános hivatkozásokban). Különböző problémákat vizsgáltunk algoritmikus szempontból, beleértve a kereskedelmi utazó problémáját, a hullámok problémáit és az udvariasabb utakat. Még mindig kevés a konzorcium hozzájárulása a témában, de ez csak a projekt célja. Dinamikus problémák a grafikonokon: A gráfokkal kapcsolatos dinamikus problémák kétféleek. – Ezek lehetnek, egyrészt a problémák bemutatott formájában kétjátékos játékok, mint például a probléma a csendőrség és a tolvaj, ahol a játék az uralom. Ezeknek a klasszikus problémáknak bőséges szakirodaloma van, ami az utóbbi időben e problémák iránti érdeklődéshez kapcsolódik. E problémák nehézsége abban rejlik, hogy a probléma megoldását stratégiában, azaz döntési fában kell bemutatni. Meyniel sejtése az egyik legnagyobb kihívás a grafikonelméletben.A konzorcium két csapata szakértelemmel rendelkezik ezekkel a problémákkal kapcsolatban. – olyan problémák is lehetnek, amelyek esetében a megoldás ellenőrzése dinamikus, iterált számítást igényel. Ez a helyzet például a perkoláció, a védőburkolatok elmozdítása (örök dominancia) vagy az erőátviteli rendszer alkalmazásai esetében. Az utóbbi témában a projektgazdát a közelmúltban felkérték, hogy írjon könyvfejezetet. (Lásd a kérelemfájlt.) (Hungarian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
V komunitě dynamických grafů existuje v průměru několik přístupů k analýze: — inkrementální analýza algoritmů: struktura dat udržuje invarianty na dynamickém grafu během jeho vývoje je to složitost v průměru dotazů na tuto strukturu, která je analyzována – Dynamic Erdös-Rényi model: Suppresions a přírůstky hran jsou vykresleny náhodně v každém kroku času. — omezený náhodný model: o akci přidávání nebo odstraňování hran rozhoduje soupeř, ale upravený hřeben je nakreslen náhodně. Mnoho prací v analytických kombinátorech existuje kolem průměrné analýzy algoritmů pracujících na statických grafech označených (nebo ne). V poslední době se objevuje práce na analýze grafů s omezenými štítky (růst štítků podél cesty, opakování štítků). Náhodné generování: Stav techniky je rozdělen do tří částí: ad hoc generátory pro různé aplikace (viární sítě a telekomunikační sítě), obecnější algoritmy (metoda Boltzmann a Monte-Carlo) a relativně jednoduché simulace modelů náhodných grafů (Erdös-Rényi, Watts-Strogatz a Barabási). První část se skládá z příspěvků LITIS, druhá je specialitou Greyc a poslední část je dobře známá oběma partnerům. Vzhledem k tomuto společnému jazyku chceme sdílet své odborné znalosti, abychom zlepšili stav techniky v obou komunitách. Algoritmické dynamické grafy: Literatura o algoritmech pro dynamické grafy obvykle začíná od aplikací a snaží se vyřešit konkrétní problém související s touto aplikací. Referenční dokument, v němž jsou uvedeny různé souvislosti, je kontext Holmes (2015, v obecných odkazech). Z algoritmického hlediska byly zkoumány různé problémy, včetně problému komerčního cestovatele, problémů vln a zdvořilějších cest. Stále existuje jen málo příspěvků konsorcia na toto téma, ale to je jen cíl projektu. Dynamické problémy na grafech: Dynamické problémy s grafy jsou dvou druhů. — Mohou být, na jedné straně, problémy prezentovány ve formě dvou hráčů hry, jako je problém četníků a zloděj, kde hra o nadvládu. Tyto klasické problémy mají bohatou literaturu spojenou s nedávným zájmem o tyto problémy. Obtížnost těchto problémů spočívá v tom, že řešení tohoto problému musí být prezentována ve formě strategie, tedy rozhodovacího stromu. Meyniel domněnka je jedním z hlavních výzev v teorii grafů.Dva týmy konsorcia mají odborné znalosti o těchto problémech. — mohou také spočívat v problémech, pro které ověření řešení vyžaduje dynamický, iterovaný výpočet. Tak je tomu například v případě problémů s perkolací, řazením ochranných krytů (věčná nadvláda) nebo dominací energie pro aplikace do rozvodných sítí. Pokud jde o posledně uvedené téma, předkladatel projektu byl nedávno požádán, aby napsal kapitolu knihy. (Viz soubor žádosti.) (Czech) | |||||||||||||||
| Property / summary: V komunitě dynamických grafů existuje v průměru několik přístupů k analýze: — inkrementální analýza algoritmů: struktura dat udržuje invarianty na dynamickém grafu během jeho vývoje je to složitost v průměru dotazů na tuto strukturu, která je analyzována – Dynamic Erdös-Rényi model: Suppresions a přírůstky hran jsou vykresleny náhodně v každém kroku času. — omezený náhodný model: o akci přidávání nebo odstraňování hran rozhoduje soupeř, ale upravený hřeben je nakreslen náhodně. Mnoho prací v analytických kombinátorech existuje kolem průměrné analýzy algoritmů pracujících na statických grafech označených (nebo ne). V poslední době se objevuje práce na analýze grafů s omezenými štítky (růst štítků podél cesty, opakování štítků). Náhodné generování: Stav techniky je rozdělen do tří částí: ad hoc generátory pro různé aplikace (viární sítě a telekomunikační sítě), obecnější algoritmy (metoda Boltzmann a Monte-Carlo) a relativně jednoduché simulace modelů náhodných grafů (Erdös-Rényi, Watts-Strogatz a Barabási). První část se skládá z příspěvků LITIS, druhá je specialitou Greyc a poslední část je dobře známá oběma partnerům. Vzhledem k tomuto společnému jazyku chceme sdílet své odborné znalosti, abychom zlepšili stav techniky v obou komunitách. Algoritmické dynamické grafy: Literatura o algoritmech pro dynamické grafy obvykle začíná od aplikací a snaží se vyřešit konkrétní problém související s touto aplikací. Referenční dokument, v němž jsou uvedeny různé souvislosti, je kontext Holmes (2015, v obecných odkazech). Z algoritmického hlediska byly zkoumány různé problémy, včetně problému komerčního cestovatele, problémů vln a zdvořilějších cest. Stále existuje jen málo příspěvků konsorcia na toto téma, ale to je jen cíl projektu. Dynamické problémy na grafech: Dynamické problémy s grafy jsou dvou druhů. — Mohou být, na jedné straně, problémy prezentovány ve formě dvou hráčů hry, jako je problém četníků a zloděj, kde hra o nadvládu. Tyto klasické problémy mají bohatou literaturu spojenou s nedávným zájmem o tyto problémy. Obtížnost těchto problémů spočívá v tom, že řešení tohoto problému musí být prezentována ve formě strategie, tedy rozhodovacího stromu. Meyniel domněnka je jedním z hlavních výzev v teorii grafů.Dva týmy konsorcia mají odborné znalosti o těchto problémech. — mohou také spočívat v problémech, pro které ověření řešení vyžaduje dynamický, iterovaný výpočet. Tak je tomu například v případě problémů s perkolací, řazením ochranných krytů (věčná nadvláda) nebo dominací energie pro aplikace do rozvodných sítí. Pokud jde o posledně uvedené téma, předkladatel projektu byl nedávno požádán, aby napsal kapitolu knihy. (Viz soubor žádosti.) (Czech) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: V komunitě dynamických grafů existuje v průměru několik přístupů k analýze: — inkrementální analýza algoritmů: struktura dat udržuje invarianty na dynamickém grafu během jeho vývoje je to složitost v průměru dotazů na tuto strukturu, která je analyzována – Dynamic Erdös-Rényi model: Suppresions a přírůstky hran jsou vykresleny náhodně v každém kroku času. — omezený náhodný model: o akci přidávání nebo odstraňování hran rozhoduje soupeř, ale upravený hřeben je nakreslen náhodně. Mnoho prací v analytických kombinátorech existuje kolem průměrné analýzy algoritmů pracujících na statických grafech označených (nebo ne). V poslední době se objevuje práce na analýze grafů s omezenými štítky (růst štítků podél cesty, opakování štítků). Náhodné generování: Stav techniky je rozdělen do tří částí: ad hoc generátory pro různé aplikace (viární sítě a telekomunikační sítě), obecnější algoritmy (metoda Boltzmann a Monte-Carlo) a relativně jednoduché simulace modelů náhodných grafů (Erdös-Rényi, Watts-Strogatz a Barabási). První část se skládá z příspěvků LITIS, druhá je specialitou Greyc a poslední část je dobře známá oběma partnerům. Vzhledem k tomuto společnému jazyku chceme sdílet své odborné znalosti, abychom zlepšili stav techniky v obou komunitách. Algoritmické dynamické grafy: Literatura o algoritmech pro dynamické grafy obvykle začíná od aplikací a snaží se vyřešit konkrétní problém související s touto aplikací. Referenční dokument, v němž jsou uvedeny různé souvislosti, je kontext Holmes (2015, v obecných odkazech). Z algoritmického hlediska byly zkoumány různé problémy, včetně problému komerčního cestovatele, problémů vln a zdvořilějších cest. Stále existuje jen málo příspěvků konsorcia na toto téma, ale to je jen cíl projektu. Dynamické problémy na grafech: Dynamické problémy s grafy jsou dvou druhů. — Mohou být, na jedné straně, problémy prezentovány ve formě dvou hráčů hry, jako je problém četníků a zloděj, kde hra o nadvládu. Tyto klasické problémy mají bohatou literaturu spojenou s nedávným zájmem o tyto problémy. Obtížnost těchto problémů spočívá v tom, že řešení tohoto problému musí být prezentována ve formě strategie, tedy rozhodovacího stromu. Meyniel domněnka je jedním z hlavních výzev v teorii grafů.Dva týmy konsorcia mají odborné znalosti o těchto problémech. — mohou také spočívat v problémech, pro které ověření řešení vyžaduje dynamický, iterovaný výpočet. Tak je tomu například v případě problémů s perkolací, řazením ochranných krytů (věčná nadvláda) nebo dominací energie pro aplikace do rozvodných sítí. Pokud jde o posledně uvedené téma, předkladatel projektu byl nedávno požádán, aby napsal kapitolu knihy. (Viz soubor žádosti.) (Czech) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
Dinamisko diagrammu kopienai ir vairākas pieejas analīzei vidēji: — inkrementālā algoritma analīze: datu struktūra uztur mainīgos elementus dinamiskajā grafikā tās evolūcijas laikā tā ir šīs struktūras vaicājumu sarežģītība, kas tiek analizēta — Dynamic Erdös-Rényi modelis: Suppresions un papildinājumi malām tiek sastādīti nejauši katrā laika posmā. — ierobežota nejaušības principa modelis: malu pievienošanas vai noņemšanas darbību izlemj pretinieks, bet modificētā kores tiek izvilkta nejauši. Daudzi darbi analītiskajās kombinatorijās pastāv ap to algoritmu vidējo analīzi, kas darbojas ar statiskajām diagrammām (vai ne). Pēdējā laikā notiek darbs pie grafikas analīzes ar ierobežotām etiķetēm (marķējumu augšana pa ceļam, etiķešu atkārtošana). Nejaušā ģenerēšana: Jaunākie sasniegumi ir sadalīti trīs daļās: ad hoc nejauši ģeneratori dažādiem lietojumiem (vijo tīkli un telekomunikāciju tīkli), vispārīgāki algoritmi (Boltzmann un Monte-Carlo metode) un salīdzinoši vienkārši modelējami nejaušu grafiku modeļi (Erdös-Rényi, Watts-Strogatz un Barabási). Pirmā daļa sastāv no LITIS iemaksām, otrā ir Greyc specialitāte, un pēdējā daļa ir labi zināma abiem partneriem. Ņemot vērā šo kopīgo valodu, mēs vēlamies dalīties pieredzē, lai uzlabotu jaunākos sasniegumus abās kopienās. Algoritmiskie dinamiskie grafiki: Literatūra par dinamisko grafiku algoritmiem parasti sākas no lietojumprogrammām un cenšas atrisināt konkrētu problēmu, kas saistīta ar šo lietojumprogrammu. Atsauces dokuments, kurā uzskaitīti dažādie konteksti, ir Holmes (2015. gads, vispārīgajās atsaucēs). No algoritmiskā viedokļa ir pētītas dažādas problēmas, tostarp komerciālā ceļotāja problēma, viļņu problēmas un vairāk pieklājīgu ceļu. Konsorcijs par šo jautājumu joprojām sniedz maz ieguldījumu, bet tas ir tikai projekta mērķis. Dinamiskās problēmas grafikos: Dinamiskās problēmas ar grafikiem ir divu veidu. — Tie var būt, no vienas puses, problēmas, kas iesniegtas kā divu spēlētāju spēles, piemēram, problēma žandarmiem un zaglis, kur spēle dominēšanu. Šīs klasiskās problēmas ir bagātas literatūrā, kas saistīta ar neseno interesi par šiemproblēmām. Šo problēmu sarežģī fakts, ka problēmas risinājumi ir jāsniedz stratēģijas veidā, tātad — lēmumu pieņemšanas shēmā. Meyniel pieņēmumi ir viens no galvenajiem izaicinājumiem graph teorijā. Abām konsorcija komandām ir zināšanas par šīm problēmām. — tās var ietvert arī problēmas, kuru dēļ risinājuma pārbaudei ir vajadzīgs dinamisks un atkārtots aprēķins. Tas attiecas, piemēram, uz problēmām, kas saistītas ar perkolāciju, aizsargu maiņu (mūžīgā dominēšana) vai elektroenerģijas domināciju izmantošanai elektrotīklos. Par pēdējo minēto tematu projekta virzītājs nesen tika aicināts uzrakstīt grāmatu nodaļu. (Skatīt pieteikuma datni.) (Latvian) | |||||||||||||||
| Property / summary: Dinamisko diagrammu kopienai ir vairākas pieejas analīzei vidēji: — inkrementālā algoritma analīze: datu struktūra uztur mainīgos elementus dinamiskajā grafikā tās evolūcijas laikā tā ir šīs struktūras vaicājumu sarežģītība, kas tiek analizēta — Dynamic Erdös-Rényi modelis: Suppresions un papildinājumi malām tiek sastādīti nejauši katrā laika posmā. — ierobežota nejaušības principa modelis: malu pievienošanas vai noņemšanas darbību izlemj pretinieks, bet modificētā kores tiek izvilkta nejauši. Daudzi darbi analītiskajās kombinatorijās pastāv ap to algoritmu vidējo analīzi, kas darbojas ar statiskajām diagrammām (vai ne). Pēdējā laikā notiek darbs pie grafikas analīzes ar ierobežotām etiķetēm (marķējumu augšana pa ceļam, etiķešu atkārtošana). Nejaušā ģenerēšana: Jaunākie sasniegumi ir sadalīti trīs daļās: ad hoc nejauši ģeneratori dažādiem lietojumiem (vijo tīkli un telekomunikāciju tīkli), vispārīgāki algoritmi (Boltzmann un Monte-Carlo metode) un salīdzinoši vienkārši modelējami nejaušu grafiku modeļi (Erdös-Rényi, Watts-Strogatz un Barabási). Pirmā daļa sastāv no LITIS iemaksām, otrā ir Greyc specialitāte, un pēdējā daļa ir labi zināma abiem partneriem. Ņemot vērā šo kopīgo valodu, mēs vēlamies dalīties pieredzē, lai uzlabotu jaunākos sasniegumus abās kopienās. Algoritmiskie dinamiskie grafiki: Literatūra par dinamisko grafiku algoritmiem parasti sākas no lietojumprogrammām un cenšas atrisināt konkrētu problēmu, kas saistīta ar šo lietojumprogrammu. Atsauces dokuments, kurā uzskaitīti dažādie konteksti, ir Holmes (2015. gads, vispārīgajās atsaucēs). No algoritmiskā viedokļa ir pētītas dažādas problēmas, tostarp komerciālā ceļotāja problēma, viļņu problēmas un vairāk pieklājīgu ceļu. Konsorcijs par šo jautājumu joprojām sniedz maz ieguldījumu, bet tas ir tikai projekta mērķis. Dinamiskās problēmas grafikos: Dinamiskās problēmas ar grafikiem ir divu veidu. — Tie var būt, no vienas puses, problēmas, kas iesniegtas kā divu spēlētāju spēles, piemēram, problēma žandarmiem un zaglis, kur spēle dominēšanu. Šīs klasiskās problēmas ir bagātas literatūrā, kas saistīta ar neseno interesi par šiemproblēmām. Šo problēmu sarežģī fakts, ka problēmas risinājumi ir jāsniedz stratēģijas veidā, tātad — lēmumu pieņemšanas shēmā. Meyniel pieņēmumi ir viens no galvenajiem izaicinājumiem graph teorijā. Abām konsorcija komandām ir zināšanas par šīm problēmām. — tās var ietvert arī problēmas, kuru dēļ risinājuma pārbaudei ir vajadzīgs dinamisks un atkārtots aprēķins. Tas attiecas, piemēram, uz problēmām, kas saistītas ar perkolāciju, aizsargu maiņu (mūžīgā dominēšana) vai elektroenerģijas domināciju izmantošanai elektrotīklos. Par pēdējo minēto tematu projekta virzītājs nesen tika aicināts uzrakstīt grāmatu nodaļu. (Skatīt pieteikuma datni.) (Latvian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Dinamisko diagrammu kopienai ir vairākas pieejas analīzei vidēji: — inkrementālā algoritma analīze: datu struktūra uztur mainīgos elementus dinamiskajā grafikā tās evolūcijas laikā tā ir šīs struktūras vaicājumu sarežģītība, kas tiek analizēta — Dynamic Erdös-Rényi modelis: Suppresions un papildinājumi malām tiek sastādīti nejauši katrā laika posmā. — ierobežota nejaušības principa modelis: malu pievienošanas vai noņemšanas darbību izlemj pretinieks, bet modificētā kores tiek izvilkta nejauši. Daudzi darbi analītiskajās kombinatorijās pastāv ap to algoritmu vidējo analīzi, kas darbojas ar statiskajām diagrammām (vai ne). Pēdējā laikā notiek darbs pie grafikas analīzes ar ierobežotām etiķetēm (marķējumu augšana pa ceļam, etiķešu atkārtošana). Nejaušā ģenerēšana: Jaunākie sasniegumi ir sadalīti trīs daļās: ad hoc nejauši ģeneratori dažādiem lietojumiem (vijo tīkli un telekomunikāciju tīkli), vispārīgāki algoritmi (Boltzmann un Monte-Carlo metode) un salīdzinoši vienkārši modelējami nejaušu grafiku modeļi (Erdös-Rényi, Watts-Strogatz un Barabási). Pirmā daļa sastāv no LITIS iemaksām, otrā ir Greyc specialitāte, un pēdējā daļa ir labi zināma abiem partneriem. Ņemot vērā šo kopīgo valodu, mēs vēlamies dalīties pieredzē, lai uzlabotu jaunākos sasniegumus abās kopienās. Algoritmiskie dinamiskie grafiki: Literatūra par dinamisko grafiku algoritmiem parasti sākas no lietojumprogrammām un cenšas atrisināt konkrētu problēmu, kas saistīta ar šo lietojumprogrammu. Atsauces dokuments, kurā uzskaitīti dažādie konteksti, ir Holmes (2015. gads, vispārīgajās atsaucēs). No algoritmiskā viedokļa ir pētītas dažādas problēmas, tostarp komerciālā ceļotāja problēma, viļņu problēmas un vairāk pieklājīgu ceļu. Konsorcijs par šo jautājumu joprojām sniedz maz ieguldījumu, bet tas ir tikai projekta mērķis. Dinamiskās problēmas grafikos: Dinamiskās problēmas ar grafikiem ir divu veidu. — Tie var būt, no vienas puses, problēmas, kas iesniegtas kā divu spēlētāju spēles, piemēram, problēma žandarmiem un zaglis, kur spēle dominēšanu. Šīs klasiskās problēmas ir bagātas literatūrā, kas saistīta ar neseno interesi par šiemproblēmām. Šo problēmu sarežģī fakts, ka problēmas risinājumi ir jāsniedz stratēģijas veidā, tātad — lēmumu pieņemšanas shēmā. Meyniel pieņēmumi ir viens no galvenajiem izaicinājumiem graph teorijā. Abām konsorcija komandām ir zināšanas par šīm problēmām. — tās var ietvert arī problēmas, kuru dēļ risinājuma pārbaudei ir vajadzīgs dinamisks un atkārtots aprēķins. Tas attiecas, piemēram, uz problēmām, kas saistītas ar perkolāciju, aizsargu maiņu (mūžīgā dominēšana) vai elektroenerģijas domināciju izmantošanai elektrotīklos. Par pēdējo minēto tematu projekta virzītājs nesen tika aicināts uzrakstīt grāmatu nodaļu. (Skatīt pieteikuma datni.) (Latvian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
Sna graif dhinimiciúla tá roinnt cur chuige ann don anailís ar an meán: — anailís incriminteach algartam: struchtúr sonraí Coinníonn invariants ar an graf dinimiciúil le linn a éabhlóide go bhfuil sé thecomplexity ar an meán na n-iarratas ar an struchtúr a bhfuil anailís déanta — Dynamic Erdös-Rényi samhail: Déantar soláthairtí agus breiseanna imill a tharraingt go randamach ag gach céim den am. — samhail randamach theoranta: is é an comhraic a chinneann an gníomh a bhaineann le himill a chur leis nó a bhaint ach tarraingítear an iomaire modhnaithe go randamach. Tá go leor oibre i gcombinatorials anailíseacha thart ar an meán anailís ar algartaim ag feidhmiú ar graif statacha lipéadaithe (nó nach bhfuil). Le déanaí, tá obair ag teacht chun cinn ar anailís graf le lipéid shrianta (fás lipéad feadh na slí, lipéid athdhéanta). Giniúint randamach: Tá staid na healaíne roinnte ina thrí chuid: gineadóirí randamacha ad-hoc d’iarratais éagsúla (líonraíviacha agus líonraí teileachumarsáide), algartaim níos cineálaí (modh Boltzmann agus Monte-Carlo) agus réasúnta simplí samhlacha graf randamach a ionsamhlú (Erdös-Rényi, Watts-Strogatz agus Barabási). Is éard atá sa chéad chuid ná aighneachtaí ó litis, is speisialtacht GREYC an dara ceann agus tá an chuid dheireanach ar eolas go maith ag an dá chomhpháirtí. I bhfianaise na teanga coitinne seo, ba mhaith linn ár saineolas a roinnt chun feabhas a chur ar an úrscothacht sa dá phobal. Graif dhinimiciúla algartamacha: Tosaíonn an litríocht ar algartaim le haghaidh graif dhinimiciúla go ginearálta ó iarratais agus féachann sé le fadhb shonrach a bhaineann leis an iarratas seo a réiteach. Is é an páipéar tagartha a liostú na comhthéacsanna éagsúla sin de Holmes (2015, sna tagairtí ginearálta). Fadhbanna éagsúla a ndearnadh staidéar orthu ó thaobh algartamach de, lena n-áirítear an fhadhb an lucht siúil tráchtála, fadhbanna na dtonnta, agus cosáin cúirtéise níos mó. Níl mórán rannchuidithe fós ón gcuibhreannas ar an ábhar, ach níl ansin ach cuspóir an tionscadail. Fadhbanna dinimiciúla ar ghraif: Tá dhá chineál fadhbanna dinimiciúla le graif. — Is féidir leo a bheith, ar thaobh amháin, fadhbanna i láthair i bhfoirm cluichí dhá-imreoir, mar shampla an fhadhb gendarmes agus an thief, i gcás an cluiche de forlámhas. Tá na fadhbanna clasaiceach litríocht flúirseach nasctha leis an spéis le déanaí sna fadhbanna seo. Is é an deacracht a bhaineann leis na fadhbanna seo ná go gcaithfear na réitigh ar an bhfadhb a chur i láthair i bhfoirm straitéise, dá bhrí sin crann cinnteoireachta. Tá tuairim Meyniel ar cheann de na dúshláin is mó i graf teoiric.Tá an dá fhoireann an cuibhreannas saineolas ar na fadhbanna seo. — d’fhéadfadh fadhbanna a bheith i gceist leo freisin a dteastaíonn ríomh dinimiciúil, atrialáilte ina leith chun an réiteach a fhíorú. Is amhlaidh atá, mar shampla, leis na fadhbanna a bhaineann le síothlú, gardaí aistrithe (forlámhas seachtrach) nó forlámhas cumhachta d’iarratais ar ghreillí cumhachta. Ar an ábhar deireanach sin, iarradh ar thionscnóir an tionscadail le déanaí caibidil leabhar a scríobh. (Féach an comhad iarratais.) (Irish) | |||||||||||||||
| Property / summary: Sna graif dhinimiciúla tá roinnt cur chuige ann don anailís ar an meán: — anailís incriminteach algartam: struchtúr sonraí Coinníonn invariants ar an graf dinimiciúil le linn a éabhlóide go bhfuil sé thecomplexity ar an meán na n-iarratas ar an struchtúr a bhfuil anailís déanta — Dynamic Erdös-Rényi samhail: Déantar soláthairtí agus breiseanna imill a tharraingt go randamach ag gach céim den am. — samhail randamach theoranta: is é an comhraic a chinneann an gníomh a bhaineann le himill a chur leis nó a bhaint ach tarraingítear an iomaire modhnaithe go randamach. Tá go leor oibre i gcombinatorials anailíseacha thart ar an meán anailís ar algartaim ag feidhmiú ar graif statacha lipéadaithe (nó nach bhfuil). Le déanaí, tá obair ag teacht chun cinn ar anailís graf le lipéid shrianta (fás lipéad feadh na slí, lipéid athdhéanta). Giniúint randamach: Tá staid na healaíne roinnte ina thrí chuid: gineadóirí randamacha ad-hoc d’iarratais éagsúla (líonraíviacha agus líonraí teileachumarsáide), algartaim níos cineálaí (modh Boltzmann agus Monte-Carlo) agus réasúnta simplí samhlacha graf randamach a ionsamhlú (Erdös-Rényi, Watts-Strogatz agus Barabási). Is éard atá sa chéad chuid ná aighneachtaí ó litis, is speisialtacht GREYC an dara ceann agus tá an chuid dheireanach ar eolas go maith ag an dá chomhpháirtí. I bhfianaise na teanga coitinne seo, ba mhaith linn ár saineolas a roinnt chun feabhas a chur ar an úrscothacht sa dá phobal. Graif dhinimiciúla algartamacha: Tosaíonn an litríocht ar algartaim le haghaidh graif dhinimiciúla go ginearálta ó iarratais agus féachann sé le fadhb shonrach a bhaineann leis an iarratas seo a réiteach. Is é an páipéar tagartha a liostú na comhthéacsanna éagsúla sin de Holmes (2015, sna tagairtí ginearálta). Fadhbanna éagsúla a ndearnadh staidéar orthu ó thaobh algartamach de, lena n-áirítear an fhadhb an lucht siúil tráchtála, fadhbanna na dtonnta, agus cosáin cúirtéise níos mó. Níl mórán rannchuidithe fós ón gcuibhreannas ar an ábhar, ach níl ansin ach cuspóir an tionscadail. Fadhbanna dinimiciúla ar ghraif: Tá dhá chineál fadhbanna dinimiciúla le graif. — Is féidir leo a bheith, ar thaobh amháin, fadhbanna i láthair i bhfoirm cluichí dhá-imreoir, mar shampla an fhadhb gendarmes agus an thief, i gcás an cluiche de forlámhas. Tá na fadhbanna clasaiceach litríocht flúirseach nasctha leis an spéis le déanaí sna fadhbanna seo. Is é an deacracht a bhaineann leis na fadhbanna seo ná go gcaithfear na réitigh ar an bhfadhb a chur i láthair i bhfoirm straitéise, dá bhrí sin crann cinnteoireachta. Tá tuairim Meyniel ar cheann de na dúshláin is mó i graf teoiric.Tá an dá fhoireann an cuibhreannas saineolas ar na fadhbanna seo. — d’fhéadfadh fadhbanna a bheith i gceist leo freisin a dteastaíonn ríomh dinimiciúil, atrialáilte ina leith chun an réiteach a fhíorú. Is amhlaidh atá, mar shampla, leis na fadhbanna a bhaineann le síothlú, gardaí aistrithe (forlámhas seachtrach) nó forlámhas cumhachta d’iarratais ar ghreillí cumhachta. Ar an ábhar deireanach sin, iarradh ar thionscnóir an tionscadail le déanaí caibidil leabhar a scríobh. (Féach an comhad iarratais.) (Irish) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Sna graif dhinimiciúla tá roinnt cur chuige ann don anailís ar an meán: — anailís incriminteach algartam: struchtúr sonraí Coinníonn invariants ar an graf dinimiciúil le linn a éabhlóide go bhfuil sé thecomplexity ar an meán na n-iarratas ar an struchtúr a bhfuil anailís déanta — Dynamic Erdös-Rényi samhail: Déantar soláthairtí agus breiseanna imill a tharraingt go randamach ag gach céim den am. — samhail randamach theoranta: is é an comhraic a chinneann an gníomh a bhaineann le himill a chur leis nó a bhaint ach tarraingítear an iomaire modhnaithe go randamach. Tá go leor oibre i gcombinatorials anailíseacha thart ar an meán anailís ar algartaim ag feidhmiú ar graif statacha lipéadaithe (nó nach bhfuil). Le déanaí, tá obair ag teacht chun cinn ar anailís graf le lipéid shrianta (fás lipéad feadh na slí, lipéid athdhéanta). Giniúint randamach: Tá staid na healaíne roinnte ina thrí chuid: gineadóirí randamacha ad-hoc d’iarratais éagsúla (líonraíviacha agus líonraí teileachumarsáide), algartaim níos cineálaí (modh Boltzmann agus Monte-Carlo) agus réasúnta simplí samhlacha graf randamach a ionsamhlú (Erdös-Rényi, Watts-Strogatz agus Barabási). Is éard atá sa chéad chuid ná aighneachtaí ó litis, is speisialtacht GREYC an dara ceann agus tá an chuid dheireanach ar eolas go maith ag an dá chomhpháirtí. I bhfianaise na teanga coitinne seo, ba mhaith linn ár saineolas a roinnt chun feabhas a chur ar an úrscothacht sa dá phobal. Graif dhinimiciúla algartamacha: Tosaíonn an litríocht ar algartaim le haghaidh graif dhinimiciúla go ginearálta ó iarratais agus féachann sé le fadhb shonrach a bhaineann leis an iarratas seo a réiteach. Is é an páipéar tagartha a liostú na comhthéacsanna éagsúla sin de Holmes (2015, sna tagairtí ginearálta). Fadhbanna éagsúla a ndearnadh staidéar orthu ó thaobh algartamach de, lena n-áirítear an fhadhb an lucht siúil tráchtála, fadhbanna na dtonnta, agus cosáin cúirtéise níos mó. Níl mórán rannchuidithe fós ón gcuibhreannas ar an ábhar, ach níl ansin ach cuspóir an tionscadail. Fadhbanna dinimiciúla ar ghraif: Tá dhá chineál fadhbanna dinimiciúla le graif. — Is féidir leo a bheith, ar thaobh amháin, fadhbanna i láthair i bhfoirm cluichí dhá-imreoir, mar shampla an fhadhb gendarmes agus an thief, i gcás an cluiche de forlámhas. Tá na fadhbanna clasaiceach litríocht flúirseach nasctha leis an spéis le déanaí sna fadhbanna seo. Is é an deacracht a bhaineann leis na fadhbanna seo ná go gcaithfear na réitigh ar an bhfadhb a chur i láthair i bhfoirm straitéise, dá bhrí sin crann cinnteoireachta. Tá tuairim Meyniel ar cheann de na dúshláin is mó i graf teoiric.Tá an dá fhoireann an cuibhreannas saineolas ar na fadhbanna seo. — d’fhéadfadh fadhbanna a bheith i gceist leo freisin a dteastaíonn ríomh dinimiciúil, atrialáilte ina leith chun an réiteach a fhíorú. Is amhlaidh atá, mar shampla, leis na fadhbanna a bhaineann le síothlú, gardaí aistrithe (forlámhas seachtrach) nó forlámhas cumhachta d’iarratais ar ghreillí cumhachta. Ar an ábhar deireanach sin, iarradh ar thionscnóir an tionscadail le déanaí caibidil leabhar a scríobh. (Féach an comhad iarratais.) (Irish) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
V dinamičnih grafih skupnost obstaja več pristopov za analizo v povprečju: — analiza dodatnega algoritma: struktura podatkov ohranja invariante na dinamičnem grafu med njegovim razvojem je kompleksnost v povprečju poizvedb v tej strukturi, ki se analizira – Dynamic Erdös-Rényi model: Suppresioni in dodatki robov se naključno narišejo na vsakem koraku. — omejeni naključni model: dejanje dodajanja ali odstranjevanja robov odloča nasprotnik, vendar je spremenjeni greben sestavljen naključno. Veliko dela v analitičnih kombinatorjih obstaja okoli povprečne analize algoritmov, ki delujejo na statičnih grafih, označenih (ali ne). V zadnjem času se začenja delo v zvezi z analizo grafov z omejenimi oznakami (rast oznak na poti, ponavljanje oznak). Naključna generacija: Stanje tehnike je razdeljeno na tri dele: ad-hoc naključni generatorji za različne aplikacije (viarska omrežja in telekomunikacijska omrežja), bolj generični algoritmi (metoda Boltzmann in Monte-Carlo) in razmeroma preprosti za simulacijo naključnih grafov (Erdös-Rényi, Watts-Strogatz in Barabási). Prvi del sestavljajo prispevki LITIS, drugi je posebnost Greyca, zadnji del pa je dobro znan obema partnerjema. Glede na ta skupni jezik želimo deliti svoje strokovno znanje za izboljšanje stanja tehnike v obeh skupnostih. Algoritemski dinamični grafi: Literatura o algoritmih za dinamične grafe se običajno začne z aplikacijami in skuša rešiti specifičen problem, povezan s to aplikacijo. Referenčni dokument, v katerem so navedeni različni konteksti, je dokument družbe Holmes (2015, v splošnih referencah). Z algoritemskega vidika so bili preučeni različni problemi, vključno s problemom komercialnega potnika, problemi valov in bolj vljudnostnimi potmi. Še vedno je malo prispevkov konzorcija na to temo, vendar je to samo cilj projekta. Dinamične težave na grafih: Dinamične težave z grafi so dveh vrst. — Po eni strani so lahko problemi, predstavljeni v obliki dvoigralskih iger, kot je problem žandarmov in tatu, kjer je igra dominacije. Ti klasični problemi imajo bogato literaturo, povezano z nedavnim zanimanjem za te težave. Težava teh težav je v tem, da morajo biti rešitve problema predstavljene v obliki strategije, s tem pa tudi v obliki drevesa odločanja. Meynielova domneva je eden od glavnih izzivov v teoriji grafov. Dve ekipi konzorcija imata strokovno znanje o teh težavah. — lahko so sestavljeni tudi iz težav, za katere preverjanje rešitve zahteva dinamičen, iteriran izračun. To velja na primer pri problemih perkolacije, premikanja varoval (večna dominacija) ali dominacije moči za aplikacije v električna omrežja. V zvezi s slednjim je bil predlagatelj projekta pred kratkim pozvan, naj napiše poglavje o knjigi. (Glej prijavno dokumentacijo.) (Slovenian) | |||||||||||||||
| Property / summary: V dinamičnih grafih skupnost obstaja več pristopov za analizo v povprečju: — analiza dodatnega algoritma: struktura podatkov ohranja invariante na dinamičnem grafu med njegovim razvojem je kompleksnost v povprečju poizvedb v tej strukturi, ki se analizira – Dynamic Erdös-Rényi model: Suppresioni in dodatki robov se naključno narišejo na vsakem koraku. — omejeni naključni model: dejanje dodajanja ali odstranjevanja robov odloča nasprotnik, vendar je spremenjeni greben sestavljen naključno. Veliko dela v analitičnih kombinatorjih obstaja okoli povprečne analize algoritmov, ki delujejo na statičnih grafih, označenih (ali ne). V zadnjem času se začenja delo v zvezi z analizo grafov z omejenimi oznakami (rast oznak na poti, ponavljanje oznak). Naključna generacija: Stanje tehnike je razdeljeno na tri dele: ad-hoc naključni generatorji za različne aplikacije (viarska omrežja in telekomunikacijska omrežja), bolj generični algoritmi (metoda Boltzmann in Monte-Carlo) in razmeroma preprosti za simulacijo naključnih grafov (Erdös-Rényi, Watts-Strogatz in Barabási). Prvi del sestavljajo prispevki LITIS, drugi je posebnost Greyca, zadnji del pa je dobro znan obema partnerjema. Glede na ta skupni jezik želimo deliti svoje strokovno znanje za izboljšanje stanja tehnike v obeh skupnostih. Algoritemski dinamični grafi: Literatura o algoritmih za dinamične grafe se običajno začne z aplikacijami in skuša rešiti specifičen problem, povezan s to aplikacijo. Referenčni dokument, v katerem so navedeni različni konteksti, je dokument družbe Holmes (2015, v splošnih referencah). Z algoritemskega vidika so bili preučeni različni problemi, vključno s problemom komercialnega potnika, problemi valov in bolj vljudnostnimi potmi. Še vedno je malo prispevkov konzorcija na to temo, vendar je to samo cilj projekta. Dinamične težave na grafih: Dinamične težave z grafi so dveh vrst. — Po eni strani so lahko problemi, predstavljeni v obliki dvoigralskih iger, kot je problem žandarmov in tatu, kjer je igra dominacije. Ti klasični problemi imajo bogato literaturo, povezano z nedavnim zanimanjem za te težave. Težava teh težav je v tem, da morajo biti rešitve problema predstavljene v obliki strategije, s tem pa tudi v obliki drevesa odločanja. Meynielova domneva je eden od glavnih izzivov v teoriji grafov. Dve ekipi konzorcija imata strokovno znanje o teh težavah. — lahko so sestavljeni tudi iz težav, za katere preverjanje rešitve zahteva dinamičen, iteriran izračun. To velja na primer pri problemih perkolacije, premikanja varoval (večna dominacija) ali dominacije moči za aplikacije v električna omrežja. V zvezi s slednjim je bil predlagatelj projekta pred kratkim pozvan, naj napiše poglavje o knjigi. (Glej prijavno dokumentacijo.) (Slovenian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: V dinamičnih grafih skupnost obstaja več pristopov za analizo v povprečju: — analiza dodatnega algoritma: struktura podatkov ohranja invariante na dinamičnem grafu med njegovim razvojem je kompleksnost v povprečju poizvedb v tej strukturi, ki se analizira – Dynamic Erdös-Rényi model: Suppresioni in dodatki robov se naključno narišejo na vsakem koraku. — omejeni naključni model: dejanje dodajanja ali odstranjevanja robov odloča nasprotnik, vendar je spremenjeni greben sestavljen naključno. Veliko dela v analitičnih kombinatorjih obstaja okoli povprečne analize algoritmov, ki delujejo na statičnih grafih, označenih (ali ne). V zadnjem času se začenja delo v zvezi z analizo grafov z omejenimi oznakami (rast oznak na poti, ponavljanje oznak). Naključna generacija: Stanje tehnike je razdeljeno na tri dele: ad-hoc naključni generatorji za različne aplikacije (viarska omrežja in telekomunikacijska omrežja), bolj generični algoritmi (metoda Boltzmann in Monte-Carlo) in razmeroma preprosti za simulacijo naključnih grafov (Erdös-Rényi, Watts-Strogatz in Barabási). Prvi del sestavljajo prispevki LITIS, drugi je posebnost Greyca, zadnji del pa je dobro znan obema partnerjema. Glede na ta skupni jezik želimo deliti svoje strokovno znanje za izboljšanje stanja tehnike v obeh skupnostih. Algoritemski dinamični grafi: Literatura o algoritmih za dinamične grafe se običajno začne z aplikacijami in skuša rešiti specifičen problem, povezan s to aplikacijo. Referenčni dokument, v katerem so navedeni različni konteksti, je dokument družbe Holmes (2015, v splošnih referencah). Z algoritemskega vidika so bili preučeni različni problemi, vključno s problemom komercialnega potnika, problemi valov in bolj vljudnostnimi potmi. Še vedno je malo prispevkov konzorcija na to temo, vendar je to samo cilj projekta. Dinamične težave na grafih: Dinamične težave z grafi so dveh vrst. — Po eni strani so lahko problemi, predstavljeni v obliki dvoigralskih iger, kot je problem žandarmov in tatu, kjer je igra dominacije. Ti klasični problemi imajo bogato literaturo, povezano z nedavnim zanimanjem za te težave. Težava teh težav je v tem, da morajo biti rešitve problema predstavljene v obliki strategije, s tem pa tudi v obliki drevesa odločanja. Meynielova domneva je eden od glavnih izzivov v teoriji grafov. Dve ekipi konzorcija imata strokovno znanje o teh težavah. — lahko so sestavljeni tudi iz težav, za katere preverjanje rešitve zahteva dinamičen, iteriran izračun. To velja na primer pri problemih perkolacije, premikanja varoval (večna dominacija) ali dominacije moči za aplikacije v električna omrežja. V zvezi s slednjim je bil predlagatelj projekta pred kratkim pozvan, naj napiše poglavje o knjigi. (Glej prijavno dokumentacijo.) (Slovenian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
В динамичните графики общността има няколко подхода за анализ средно: — поетапен анализ на алгоритъма: структура на даннитеподдържа invariants на динамичната графика по време на еволюцията му е сложността на средно заявки към тази структура, която се анализира — Dynamic Erdös-Rényi модел: Suppresions и допълнения на ръбове се чертаят на случаен принцип на всеки етап от времето. — ограничен произволен модел: действието на добавяне или премахване на ръбове се определя от противник, но модифицираната хребета се чертае на случаен принцип. Много работа в аналитичните комбинаториуми съществува около средния анализ на алгоритми, работещи на статични графики, етикетирани (или не). В последно време започва работа по графичен анализ с ограничени етикети (растеж на етикетите по пътя, повтаряне на етикетите). Произволно генериране: Състоянието на техниката е разделено на три части: ad-hoc случайни генератори за различни приложения (волиарни мрежи и телекомуникационни мрежи), по-общи алгоритми (метод на Болцман и Монте Карло) и сравнително прости за симулиране на случайни графични модели (Erdös-Rényi, Watts-Strogatz и Barabási). Първата част се състои от принос на LITIS, втората е специалност на Грейк, а последната е добре позната на двамата партньори. Като се има предвид този общ език, искаме да споделим нашия експертен опит за подобряване на състоянието на технологиите и в двете общности. Алгоритмични динамични графики: Литературата за алгоритмите за динамични графики обикновено започва от приложения и се стреми да реши конкретен проблем, свързан с това приложение. Референтният документ, в който се изброяват различните контексти, е този на Холмс (2015 г., в общите препратки). От алгоритмична гледна точка са проучени различни проблеми, включително проблема с търговския пътник, проблемите на вълните и по-учтивите пътища. Все още има малко мнения от консорциума по този въпрос, но това е само целта на проекта. Динамични проблеми на графиките: Динамичните проблеми с графиките са от два вида. — Те могат да бъдат, от една страна, проблеми, представени под формата на игри с двама играчи, като проблема с жандармите и крадеца, където играта на господство. Тези класически проблеми имат богата литература, свързана с неотдавнашния интерес към тези проблеми. Трудността на тези проблеми се състои във факта, че решенията на проблема трябва да бъдат представени под формата на стратегия, следователно дърво на решенията. Meyniel "и предположения е един от основните предизвикателства в графика теория.Двете екипи на консорциума имат опит по тези проблеми. — те могат да се състоят и от проблеми, за които проверката на решението изисква динамично, итерирано изчисление. Такъв е случаят например с проблемите с перколацията, изместването на предпазителите (вечно господство) или доминирането на мощността за приложения към електропреносните мрежи. По последния въпрос организаторът на проекта наскоро беше помолен да напише глава от книгата. (Вж. досието на заявлението.) (Bulgarian) | |||||||||||||||
| Property / summary: В динамичните графики общността има няколко подхода за анализ средно: — поетапен анализ на алгоритъма: структура на даннитеподдържа invariants на динамичната графика по време на еволюцията му е сложността на средно заявки към тази структура, която се анализира — Dynamic Erdös-Rényi модел: Suppresions и допълнения на ръбове се чертаят на случаен принцип на всеки етап от времето. — ограничен произволен модел: действието на добавяне или премахване на ръбове се определя от противник, но модифицираната хребета се чертае на случаен принцип. Много работа в аналитичните комбинаториуми съществува около средния анализ на алгоритми, работещи на статични графики, етикетирани (или не). В последно време започва работа по графичен анализ с ограничени етикети (растеж на етикетите по пътя, повтаряне на етикетите). Произволно генериране: Състоянието на техниката е разделено на три части: ad-hoc случайни генератори за различни приложения (волиарни мрежи и телекомуникационни мрежи), по-общи алгоритми (метод на Болцман и Монте Карло) и сравнително прости за симулиране на случайни графични модели (Erdös-Rényi, Watts-Strogatz и Barabási). Първата част се състои от принос на LITIS, втората е специалност на Грейк, а последната е добре позната на двамата партньори. Като се има предвид този общ език, искаме да споделим нашия експертен опит за подобряване на състоянието на технологиите и в двете общности. Алгоритмични динамични графики: Литературата за алгоритмите за динамични графики обикновено започва от приложения и се стреми да реши конкретен проблем, свързан с това приложение. Референтният документ, в който се изброяват различните контексти, е този на Холмс (2015 г., в общите препратки). От алгоритмична гледна точка са проучени различни проблеми, включително проблема с търговския пътник, проблемите на вълните и по-учтивите пътища. Все още има малко мнения от консорциума по този въпрос, но това е само целта на проекта. Динамични проблеми на графиките: Динамичните проблеми с графиките са от два вида. — Те могат да бъдат, от една страна, проблеми, представени под формата на игри с двама играчи, като проблема с жандармите и крадеца, където играта на господство. Тези класически проблеми имат богата литература, свързана с неотдавнашния интерес към тези проблеми. Трудността на тези проблеми се състои във факта, че решенията на проблема трябва да бъдат представени под формата на стратегия, следователно дърво на решенията. Meyniel "и предположения е един от основните предизвикателства в графика теория.Двете екипи на консорциума имат опит по тези проблеми. — те могат да се състоят и от проблеми, за които проверката на решението изисква динамично, итерирано изчисление. Такъв е случаят например с проблемите с перколацията, изместването на предпазителите (вечно господство) или доминирането на мощността за приложения към електропреносните мрежи. По последния въпрос организаторът на проекта наскоро беше помолен да напише глава от книгата. (Вж. досието на заявлението.) (Bulgarian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: В динамичните графики общността има няколко подхода за анализ средно: — поетапен анализ на алгоритъма: структура на даннитеподдържа invariants на динамичната графика по време на еволюцията му е сложността на средно заявки към тази структура, която се анализира — Dynamic Erdös-Rényi модел: Suppresions и допълнения на ръбове се чертаят на случаен принцип на всеки етап от времето. — ограничен произволен модел: действието на добавяне или премахване на ръбове се определя от противник, но модифицираната хребета се чертае на случаен принцип. Много работа в аналитичните комбинаториуми съществува около средния анализ на алгоритми, работещи на статични графики, етикетирани (или не). В последно време започва работа по графичен анализ с ограничени етикети (растеж на етикетите по пътя, повтаряне на етикетите). Произволно генериране: Състоянието на техниката е разделено на три части: ad-hoc случайни генератори за различни приложения (волиарни мрежи и телекомуникационни мрежи), по-общи алгоритми (метод на Болцман и Монте Карло) и сравнително прости за симулиране на случайни графични модели (Erdös-Rényi, Watts-Strogatz и Barabási). Първата част се състои от принос на LITIS, втората е специалност на Грейк, а последната е добре позната на двамата партньори. Като се има предвид този общ език, искаме да споделим нашия експертен опит за подобряване на състоянието на технологиите и в двете общности. Алгоритмични динамични графики: Литературата за алгоритмите за динамични графики обикновено започва от приложения и се стреми да реши конкретен проблем, свързан с това приложение. Референтният документ, в който се изброяват различните контексти, е този на Холмс (2015 г., в общите препратки). От алгоритмична гледна точка са проучени различни проблеми, включително проблема с търговския пътник, проблемите на вълните и по-учтивите пътища. Все още има малко мнения от консорциума по този въпрос, но това е само целта на проекта. Динамични проблеми на графиките: Динамичните проблеми с графиките са от два вида. — Те могат да бъдат, от една страна, проблеми, представени под формата на игри с двама играчи, като проблема с жандармите и крадеца, където играта на господство. Тези класически проблеми имат богата литература, свързана с неотдавнашния интерес към тези проблеми. Трудността на тези проблеми се състои във факта, че решенията на проблема трябва да бъдат представени под формата на стратегия, следователно дърво на решенията. Meyniel "и предположения е един от основните предизвикателства в графика теория.Двете екипи на консорциума имат опит по тези проблеми. — те могат да се състоят и от проблеми, за които проверката на решението изисква динамично, итерирано изчисление. Такъв е случаят например с проблемите с перколацията, изместването на предпазителите (вечно господство) или доминирането на мощността за приложения към електропреносните мрежи. По последния въпрос организаторът на проекта наскоро беше помолен да напише глава от книгата. (Вж. досието на заявлението.) (Bulgarian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
Fil-komunità tal-graffs dinamiċi hemm diversi approċċi għall-analiżi bħala medja: — analiżi inkrimentali algoritmu: struttura tad-data żżomm invarjanti fuq il-graff dinamika matul l-evoluzzjoni tagħha hija l-kumplessità fuq medja ta ‘mistoqsijiet għal din l-istruttura li hija analizzata — mudell Dynamic Erdös-Rényi: Suppresions u żidiet ta ‘truf huma mfassla saltwarjament f’kull pass ta’ ħin. — mudell aleatorju ristrett: l-azzjoni ta ‘żieda jew tneħħija truf huwa deċiż minn avversarju iżda l-pont modifikat huwa mfassal b’mod aleatorju. Ħafna xogħol fil-kombinazzjonijiet analitiċi jeżisti madwar l-analiżi medja ta ‘algoritmi li joperaw fuq graffs statiċi tikkettati (jew le). Aktar reċentement, qed toħroġ ħidma fuq l-analiżi tal-graff b’tikketti limitati (tkabbir ta’ tikketti tul it-triq, tikketti ripetuti). Ġenerazzjoni każwali: L-istat tal-arti huwa maqsum fi tliet partijiet: ġeneraturi każwali ad hoc għal applikazzjonijiet differenti (netwerks vjarji u netwerks tat-telekomunikazzjoni), algoritmi aktar ġeneriċi (metodu Boltzmann u Monte-Carlo) u relattivament sempliċi biex jissimulaw mudelli ta’ graff każwali (Erdös-Rényi, Watts-Strogatz u Barabási). L-ewwel parti tikkonsisti f’kontribuzzjonijiet minn LITIS, it-tieni hija speċjalità ta’ Greyc u l-aħħar parti hija magħrufa sew għaż-żewġ imsieħba. Minħabba din il-lingwa komuni, irridu naqsmu l-għarfien espert tagħna biex intejbu l-istat tal-arti fiż-żewġ komunitajiet. Graffs dinamiċi algoritmiċi: Il-letteratura dwar l-algoritmi għall-graffs dinamiċi ġeneralment tibda mill-applikazzjonijiet u tfittex li ssolvi problema speċifika relatata ma’ din l-applikazzjoni. Id-dokument ta’ referenza li jelenka l-kuntesti differenti huwa dak ta’ Holmes (2015, fir-referenzi ġenerali). Diversi problemi ġew studjati mill-perspettiva algoritmika, inkluża l-problema tal-vjaġġatur kummerċjali, problemi ta’ mewġ, u mogħdijiet aktar ta’ korteżija. Għad hemm ftit kontribuzzjonijiet mill-konsorzju dwar is-suġġett, iżda dan huwa biss l-objettiv tal-proġett. Problemi dinamiċi fuq il-graffs: Problemi dinamiċi bil-graffs huma ta ‘żewġ tipi. — Dawn jistgħu jkunu, minn naħa waħda, problemi ppreżentati fil-forma ta ‘logħob two-player, bħall-problema ta’ gendarmes u l-ħalliel, fejn il-logħba ta ‘dominazzjoni. Dawn il-problemi klassiċi għandhom ħafna letteratura marbuta ma’ l-interess reċenti f’dawn il-problemi. Id-diffikultà ta’ dawn il-problemi tinsab fil-fatt li s-soluzzjonijiet għall-problema jridu jiġu ppreżentati fil-forma ta’ strateġija, u għalhekk dijagramma tad-deċiżjonijiet. Konġettura Meyniel hija waħda mill-isfidi ewlenin fit-teorija graff. Iż-żewġ timijiet tal-konsorzju għandhom kompetenza dwar dawn il-problemi. — dawn jistgħu jikkonsistu wkoll fi problemi li għalihom il-verifika tas-soluzzjoni teħtieġ kalkolu dinamiku u iterat. Dan huwa l-każ, pereżempju, bil-problemi ta ‘perkolazzjoni, ċaqliq ta’ lqugħ (dominazzjoni eterna) jew power-domination għall-applikazzjonijiet għall-grids tal-enerġija. Dwar dan l-aħħar suġġett, il-promotur tal-proġett kien reċentement mitlub jikteb kapitolu tal-ktieb. (Ara l-fajl tal-applikazzjoni.) (Maltese) | |||||||||||||||
| Property / summary: Fil-komunità tal-graffs dinamiċi hemm diversi approċċi għall-analiżi bħala medja: — analiżi inkrimentali algoritmu: struttura tad-data żżomm invarjanti fuq il-graff dinamika matul l-evoluzzjoni tagħha hija l-kumplessità fuq medja ta ‘mistoqsijiet għal din l-istruttura li hija analizzata — mudell Dynamic Erdös-Rényi: Suppresions u żidiet ta ‘truf huma mfassla saltwarjament f’kull pass ta’ ħin. — mudell aleatorju ristrett: l-azzjoni ta ‘żieda jew tneħħija truf huwa deċiż minn avversarju iżda l-pont modifikat huwa mfassal b’mod aleatorju. Ħafna xogħol fil-kombinazzjonijiet analitiċi jeżisti madwar l-analiżi medja ta ‘algoritmi li joperaw fuq graffs statiċi tikkettati (jew le). Aktar reċentement, qed toħroġ ħidma fuq l-analiżi tal-graff b’tikketti limitati (tkabbir ta’ tikketti tul it-triq, tikketti ripetuti). Ġenerazzjoni każwali: L-istat tal-arti huwa maqsum fi tliet partijiet: ġeneraturi każwali ad hoc għal applikazzjonijiet differenti (netwerks vjarji u netwerks tat-telekomunikazzjoni), algoritmi aktar ġeneriċi (metodu Boltzmann u Monte-Carlo) u relattivament sempliċi biex jissimulaw mudelli ta’ graff każwali (Erdös-Rényi, Watts-Strogatz u Barabási). L-ewwel parti tikkonsisti f’kontribuzzjonijiet minn LITIS, it-tieni hija speċjalità ta’ Greyc u l-aħħar parti hija magħrufa sew għaż-żewġ imsieħba. Minħabba din il-lingwa komuni, irridu naqsmu l-għarfien espert tagħna biex intejbu l-istat tal-arti fiż-żewġ komunitajiet. Graffs dinamiċi algoritmiċi: Il-letteratura dwar l-algoritmi għall-graffs dinamiċi ġeneralment tibda mill-applikazzjonijiet u tfittex li ssolvi problema speċifika relatata ma’ din l-applikazzjoni. Id-dokument ta’ referenza li jelenka l-kuntesti differenti huwa dak ta’ Holmes (2015, fir-referenzi ġenerali). Diversi problemi ġew studjati mill-perspettiva algoritmika, inkluża l-problema tal-vjaġġatur kummerċjali, problemi ta’ mewġ, u mogħdijiet aktar ta’ korteżija. Għad hemm ftit kontribuzzjonijiet mill-konsorzju dwar is-suġġett, iżda dan huwa biss l-objettiv tal-proġett. Problemi dinamiċi fuq il-graffs: Problemi dinamiċi bil-graffs huma ta ‘żewġ tipi. — Dawn jistgħu jkunu, minn naħa waħda, problemi ppreżentati fil-forma ta ‘logħob two-player, bħall-problema ta’ gendarmes u l-ħalliel, fejn il-logħba ta ‘dominazzjoni. Dawn il-problemi klassiċi għandhom ħafna letteratura marbuta ma’ l-interess reċenti f’dawn il-problemi. Id-diffikultà ta’ dawn il-problemi tinsab fil-fatt li s-soluzzjonijiet għall-problema jridu jiġu ppreżentati fil-forma ta’ strateġija, u għalhekk dijagramma tad-deċiżjonijiet. Konġettura Meyniel hija waħda mill-isfidi ewlenin fit-teorija graff. Iż-żewġ timijiet tal-konsorzju għandhom kompetenza dwar dawn il-problemi. — dawn jistgħu jikkonsistu wkoll fi problemi li għalihom il-verifika tas-soluzzjoni teħtieġ kalkolu dinamiku u iterat. Dan huwa l-każ, pereżempju, bil-problemi ta ‘perkolazzjoni, ċaqliq ta’ lqugħ (dominazzjoni eterna) jew power-domination għall-applikazzjonijiet għall-grids tal-enerġija. Dwar dan l-aħħar suġġett, il-promotur tal-proġett kien reċentement mitlub jikteb kapitolu tal-ktieb. (Ara l-fajl tal-applikazzjoni.) (Maltese) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Fil-komunità tal-graffs dinamiċi hemm diversi approċċi għall-analiżi bħala medja: — analiżi inkrimentali algoritmu: struttura tad-data żżomm invarjanti fuq il-graff dinamika matul l-evoluzzjoni tagħha hija l-kumplessità fuq medja ta ‘mistoqsijiet għal din l-istruttura li hija analizzata — mudell Dynamic Erdös-Rényi: Suppresions u żidiet ta ‘truf huma mfassla saltwarjament f’kull pass ta’ ħin. — mudell aleatorju ristrett: l-azzjoni ta ‘żieda jew tneħħija truf huwa deċiż minn avversarju iżda l-pont modifikat huwa mfassal b’mod aleatorju. Ħafna xogħol fil-kombinazzjonijiet analitiċi jeżisti madwar l-analiżi medja ta ‘algoritmi li joperaw fuq graffs statiċi tikkettati (jew le). Aktar reċentement, qed toħroġ ħidma fuq l-analiżi tal-graff b’tikketti limitati (tkabbir ta’ tikketti tul it-triq, tikketti ripetuti). Ġenerazzjoni każwali: L-istat tal-arti huwa maqsum fi tliet partijiet: ġeneraturi każwali ad hoc għal applikazzjonijiet differenti (netwerks vjarji u netwerks tat-telekomunikazzjoni), algoritmi aktar ġeneriċi (metodu Boltzmann u Monte-Carlo) u relattivament sempliċi biex jissimulaw mudelli ta’ graff każwali (Erdös-Rényi, Watts-Strogatz u Barabási). L-ewwel parti tikkonsisti f’kontribuzzjonijiet minn LITIS, it-tieni hija speċjalità ta’ Greyc u l-aħħar parti hija magħrufa sew għaż-żewġ imsieħba. Minħabba din il-lingwa komuni, irridu naqsmu l-għarfien espert tagħna biex intejbu l-istat tal-arti fiż-żewġ komunitajiet. Graffs dinamiċi algoritmiċi: Il-letteratura dwar l-algoritmi għall-graffs dinamiċi ġeneralment tibda mill-applikazzjonijiet u tfittex li ssolvi problema speċifika relatata ma’ din l-applikazzjoni. Id-dokument ta’ referenza li jelenka l-kuntesti differenti huwa dak ta’ Holmes (2015, fir-referenzi ġenerali). Diversi problemi ġew studjati mill-perspettiva algoritmika, inkluża l-problema tal-vjaġġatur kummerċjali, problemi ta’ mewġ, u mogħdijiet aktar ta’ korteżija. Għad hemm ftit kontribuzzjonijiet mill-konsorzju dwar is-suġġett, iżda dan huwa biss l-objettiv tal-proġett. Problemi dinamiċi fuq il-graffs: Problemi dinamiċi bil-graffs huma ta ‘żewġ tipi. — Dawn jistgħu jkunu, minn naħa waħda, problemi ppreżentati fil-forma ta ‘logħob two-player, bħall-problema ta’ gendarmes u l-ħalliel, fejn il-logħba ta ‘dominazzjoni. Dawn il-problemi klassiċi għandhom ħafna letteratura marbuta ma’ l-interess reċenti f’dawn il-problemi. Id-diffikultà ta’ dawn il-problemi tinsab fil-fatt li s-soluzzjonijiet għall-problema jridu jiġu ppreżentati fil-forma ta’ strateġija, u għalhekk dijagramma tad-deċiżjonijiet. Konġettura Meyniel hija waħda mill-isfidi ewlenin fit-teorija graff. Iż-żewġ timijiet tal-konsorzju għandhom kompetenza dwar dawn il-problemi. — dawn jistgħu jikkonsistu wkoll fi problemi li għalihom il-verifika tas-soluzzjoni teħtieġ kalkolu dinamiku u iterat. Dan huwa l-każ, pereżempju, bil-problemi ta ‘perkolazzjoni, ċaqliq ta’ lqugħ (dominazzjoni eterna) jew power-domination għall-applikazzjonijiet għall-grids tal-enerġija. Dwar dan l-aħħar suġġett, il-promotur tal-proġett kien reċentement mitlub jikteb kapitolu tal-ktieb. (Ara l-fajl tal-applikazzjoni.) (Maltese) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
Na comunidade de gráficos dinâmicos há várias abordagens para a análise em média: — análise de algoritmos incrementais: uma estrutura de dados mantém invariantes no gráfico dinâmico durante a sua evolução é a complexidade média das consultas a esta estrutura que é analisada — modelo dinâmico de Erdös-Rényi: Supressões e adições de bordas são desenhadas aleatoriamente a cada passo do tempo. — modelo aleatório restrito: a ação de adicionar ou remover arestas é decidida por um oponente, mas a crista modificada é desenhada aleatoriamente. Muitos trabalhos em combinatória analítica existem em torno da análise média de algoritmos operando em grafos estáticos rotulados (ou não). Mais recentemente, está a emergir trabalho na análise de gráficos com etiquetas restritas (crescimento de etiquetas ao longo do caminho, repetição de etiquetas). Geração aleatória: O estado da arte divide-se em três partes: geradores aleatórios ad hoc para diferentes aplicações (redes viárias e redes de telecomunicações), algoritmos mais genéricos (método de Boltzmann e Monte-Carlo) e modelos de grafos aleatórios relativamente simples de simular (Erdös-Rényi, Watts-Strogatz e Barabási). A primeira parte é composta por contribuições da LITIS, a segunda é uma especialidade da GREYC e a última parte é bem conhecida por ambos os parceiros. Dada esta linguagem comum, queremos partilhar a nossa experiência para melhorar o estado da arte em ambas as comunidades. Gráficos dinâmicos algorítmicos: A literatura sobre algoritmos para grafos dinâmicos geralmente parte de aplicações e procura resolver um problema específico relacionado a esta aplicação. O artigo de referência que enumera os diferentes contextos é o de Holmes (2015, nas referências gerais). Vários problemas foram estudados do ponto de vista algorítmico, incluindo o problema do viajante comercial, problemas de ondas e caminhos mais corteses. Ainda há poucas contribuições do consórcio sobre o assunto, mas este é apenas o objetivo do projeto. Problemas dinâmicos em gráficos: Problemas dinâmicos com gráficos são de dois tipos. — Podem ser, por um lado, problemas apresentados sob a forma de jogos para dois jogadores, como o problema dos gendarmes e do ladrão, em que o jogo de dominação. Estes problemas clássicos têm abundante literatura ligada ao recente interesse por estesproblemas. A dificuldade destes problemas reside no facto de as soluções para o problema deverem ser apresentadas sob a forma de uma estratégia, daí uma árvore de decisão. A conjectura de Meyniel é um dos principais desafios da teoria dos grafos. As duas equipas do consórcio têm conhecimentos especializados sobre estes problemas. — podem também consistir em problemas para os quais a verificação da solução exige um cálculo dinâmico e iterado. É o caso, por exemplo, dos problemas de percolação, deslocamento de guardas (dominação eterna) ou dominação de poder para aplicações em redes elétricas. Sobre este último tema, o promotor do projeto foi recentemente convidado a escrever um capítulo de livro. (Ver processo de candidatura.) (Portuguese) | |||||||||||||||
| Property / summary: Na comunidade de gráficos dinâmicos há várias abordagens para a análise em média: — análise de algoritmos incrementais: uma estrutura de dados mantém invariantes no gráfico dinâmico durante a sua evolução é a complexidade média das consultas a esta estrutura que é analisada — modelo dinâmico de Erdös-Rényi: Supressões e adições de bordas são desenhadas aleatoriamente a cada passo do tempo. — modelo aleatório restrito: a ação de adicionar ou remover arestas é decidida por um oponente, mas a crista modificada é desenhada aleatoriamente. Muitos trabalhos em combinatória analítica existem em torno da análise média de algoritmos operando em grafos estáticos rotulados (ou não). Mais recentemente, está a emergir trabalho na análise de gráficos com etiquetas restritas (crescimento de etiquetas ao longo do caminho, repetição de etiquetas). Geração aleatória: O estado da arte divide-se em três partes: geradores aleatórios ad hoc para diferentes aplicações (redes viárias e redes de telecomunicações), algoritmos mais genéricos (método de Boltzmann e Monte-Carlo) e modelos de grafos aleatórios relativamente simples de simular (Erdös-Rényi, Watts-Strogatz e Barabási). A primeira parte é composta por contribuições da LITIS, a segunda é uma especialidade da GREYC e a última parte é bem conhecida por ambos os parceiros. Dada esta linguagem comum, queremos partilhar a nossa experiência para melhorar o estado da arte em ambas as comunidades. Gráficos dinâmicos algorítmicos: A literatura sobre algoritmos para grafos dinâmicos geralmente parte de aplicações e procura resolver um problema específico relacionado a esta aplicação. O artigo de referência que enumera os diferentes contextos é o de Holmes (2015, nas referências gerais). Vários problemas foram estudados do ponto de vista algorítmico, incluindo o problema do viajante comercial, problemas de ondas e caminhos mais corteses. Ainda há poucas contribuições do consórcio sobre o assunto, mas este é apenas o objetivo do projeto. Problemas dinâmicos em gráficos: Problemas dinâmicos com gráficos são de dois tipos. — Podem ser, por um lado, problemas apresentados sob a forma de jogos para dois jogadores, como o problema dos gendarmes e do ladrão, em que o jogo de dominação. Estes problemas clássicos têm abundante literatura ligada ao recente interesse por estesproblemas. A dificuldade destes problemas reside no facto de as soluções para o problema deverem ser apresentadas sob a forma de uma estratégia, daí uma árvore de decisão. A conjectura de Meyniel é um dos principais desafios da teoria dos grafos. As duas equipas do consórcio têm conhecimentos especializados sobre estes problemas. — podem também consistir em problemas para os quais a verificação da solução exige um cálculo dinâmico e iterado. É o caso, por exemplo, dos problemas de percolação, deslocamento de guardas (dominação eterna) ou dominação de poder para aplicações em redes elétricas. Sobre este último tema, o promotor do projeto foi recentemente convidado a escrever um capítulo de livro. (Ver processo de candidatura.) (Portuguese) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: Na comunidade de gráficos dinâmicos há várias abordagens para a análise em média: — análise de algoritmos incrementais: uma estrutura de dados mantém invariantes no gráfico dinâmico durante a sua evolução é a complexidade média das consultas a esta estrutura que é analisada — modelo dinâmico de Erdös-Rényi: Supressões e adições de bordas são desenhadas aleatoriamente a cada passo do tempo. — modelo aleatório restrito: a ação de adicionar ou remover arestas é decidida por um oponente, mas a crista modificada é desenhada aleatoriamente. Muitos trabalhos em combinatória analítica existem em torno da análise média de algoritmos operando em grafos estáticos rotulados (ou não). Mais recentemente, está a emergir trabalho na análise de gráficos com etiquetas restritas (crescimento de etiquetas ao longo do caminho, repetição de etiquetas). Geração aleatória: O estado da arte divide-se em três partes: geradores aleatórios ad hoc para diferentes aplicações (redes viárias e redes de telecomunicações), algoritmos mais genéricos (método de Boltzmann e Monte-Carlo) e modelos de grafos aleatórios relativamente simples de simular (Erdös-Rényi, Watts-Strogatz e Barabási). A primeira parte é composta por contribuições da LITIS, a segunda é uma especialidade da GREYC e a última parte é bem conhecida por ambos os parceiros. Dada esta linguagem comum, queremos partilhar a nossa experiência para melhorar o estado da arte em ambas as comunidades. Gráficos dinâmicos algorítmicos: A literatura sobre algoritmos para grafos dinâmicos geralmente parte de aplicações e procura resolver um problema específico relacionado a esta aplicação. O artigo de referência que enumera os diferentes contextos é o de Holmes (2015, nas referências gerais). Vários problemas foram estudados do ponto de vista algorítmico, incluindo o problema do viajante comercial, problemas de ondas e caminhos mais corteses. Ainda há poucas contribuições do consórcio sobre o assunto, mas este é apenas o objetivo do projeto. Problemas dinâmicos em gráficos: Problemas dinâmicos com gráficos são de dois tipos. — Podem ser, por um lado, problemas apresentados sob a forma de jogos para dois jogadores, como o problema dos gendarmes e do ladrão, em que o jogo de dominação. Estes problemas clássicos têm abundante literatura ligada ao recente interesse por estesproblemas. A dificuldade destes problemas reside no facto de as soluções para o problema deverem ser apresentadas sob a forma de uma estratégia, daí uma árvore de decisão. A conjectura de Meyniel é um dos principais desafios da teoria dos grafos. As duas equipas do consórcio têm conhecimentos especializados sobre estes problemas. — podem também consistir em problemas para os quais a verificação da solução exige um cálculo dinâmico e iterado. É o caso, por exemplo, dos problemas de percolação, deslocamento de guardas (dominação eterna) ou dominação de poder para aplicações em redes elétricas. Sobre este último tema, o promotor do projeto foi recentemente convidado a escrever um capítulo de livro. (Ver processo de candidatura.) (Portuguese) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
I de dynamiske grafer samfund er der flere tilgange til analysen i gennemsnit: — trinvis algoritmeanalyse: en datastruktur opretholder invariants på den dynamiske graf under dens udvikling det er denkompleksitet i gennemsnit af forespørgsler til denne struktur, der analyseres — Dynamic Erdös-Rényi model: Suppresions og tilføjelser af kanter tegnes tilfældigt på hvert trin i tiden. — begrænset tilfældig model: handlingen af at tilføje eller fjerne kanter besluttes af en modstander, men den modificerede højderyg trækkes tilfældigt. Mange arbejde i analytiske kombinatorier findes omkring den gennemsnitlige analyse af algoritmer, der opererer på statiske grafer mærket (eller ej). For nylig er der arbejde med grafanalyse med begrænsede etiketter (vækst af etiketter undervejs, gentagelse af etiketter). Tilfældig generation: Det aktuelle tekniske niveau er opdelt i tre dele: ad hoc tilfældige generatorer til forskellige applikationer (viære netværk og telekommunikationsnet), mere generiske algoritmer (Boltzmann og Monte-Carlo-metoden) og relativt enkle at simulere tilfældige grafmodeller (Erdös-Rényi, Watts-Strogatz og Barabási). Den første del består af bidrag fra LITIS, den anden er et speciale i Greyc, og den sidste del er velkendt for begge parter. I betragtning af dette fælles sprog ønsker vi at dele vores ekspertise for at forbedre det aktuelle tekniske niveau i begge samfund. Algoritmiske dynamiske grafer: Litteraturen om algoritmer til dynamiske grafer starter generelt fra applikationer og søger at løse et specifikt problem i forbindelse med denne applikation. Referencedokumentet, der indeholder en liste over de forskellige sammenhænge, er Holmes (2015, i de generelle henvisninger). Forskellige problemer er blevet undersøgt ud fra et algoritmisk synspunkt, herunder problemet med den kommercielle rejsende, problemer med bølger, og mere høflighed stier. Der er stadig få bidrag fra konsortiet om emnet, men det er kun projektets mål. Dynamiske problemer på grafer: Dynamiske problemer med grafer er af to slags. — De kan på den ene side være problemer i form af to-player-spil, såsom problemet med gendarmer og tyven, hvor spillet om dominans. Disse klassiske problemer har omfattende litteratur i forbindelse med den seneste tids interesse for disse problemer. Vanskelighederne ved disse problemer ligger i, at løsningerne på problemet skal præsenteres i form af en strategi og dermed et beslutningstræ. Meyniels formodninger er en af de største udfordringer i grafteori.De to hold i konsortiet har ekspertise om disse problemer. — de kan også bestå af problemer, for hvilke verifikationen af løsningen kræver en dynamisk, itereret beregning. Dette er f.eks. tilfældet med problemerne med percolation, skift vagter (evigt dominans) eller magt-dominering til applikationer til elnet. Med hensyn til sidstnævnte er projektinitiativtageren for nylig blevet bedt om at skrive et bogkapitel. (Se ansøgningsdossieret.) (Danish) | |||||||||||||||
| Property / summary: I de dynamiske grafer samfund er der flere tilgange til analysen i gennemsnit: — trinvis algoritmeanalyse: en datastruktur opretholder invariants på den dynamiske graf under dens udvikling det er denkompleksitet i gennemsnit af forespørgsler til denne struktur, der analyseres — Dynamic Erdös-Rényi model: Suppresions og tilføjelser af kanter tegnes tilfældigt på hvert trin i tiden. — begrænset tilfældig model: handlingen af at tilføje eller fjerne kanter besluttes af en modstander, men den modificerede højderyg trækkes tilfældigt. Mange arbejde i analytiske kombinatorier findes omkring den gennemsnitlige analyse af algoritmer, der opererer på statiske grafer mærket (eller ej). For nylig er der arbejde med grafanalyse med begrænsede etiketter (vækst af etiketter undervejs, gentagelse af etiketter). Tilfældig generation: Det aktuelle tekniske niveau er opdelt i tre dele: ad hoc tilfældige generatorer til forskellige applikationer (viære netværk og telekommunikationsnet), mere generiske algoritmer (Boltzmann og Monte-Carlo-metoden) og relativt enkle at simulere tilfældige grafmodeller (Erdös-Rényi, Watts-Strogatz og Barabási). Den første del består af bidrag fra LITIS, den anden er et speciale i Greyc, og den sidste del er velkendt for begge parter. I betragtning af dette fælles sprog ønsker vi at dele vores ekspertise for at forbedre det aktuelle tekniske niveau i begge samfund. Algoritmiske dynamiske grafer: Litteraturen om algoritmer til dynamiske grafer starter generelt fra applikationer og søger at løse et specifikt problem i forbindelse med denne applikation. Referencedokumentet, der indeholder en liste over de forskellige sammenhænge, er Holmes (2015, i de generelle henvisninger). Forskellige problemer er blevet undersøgt ud fra et algoritmisk synspunkt, herunder problemet med den kommercielle rejsende, problemer med bølger, og mere høflighed stier. Der er stadig få bidrag fra konsortiet om emnet, men det er kun projektets mål. Dynamiske problemer på grafer: Dynamiske problemer med grafer er af to slags. — De kan på den ene side være problemer i form af to-player-spil, såsom problemet med gendarmer og tyven, hvor spillet om dominans. Disse klassiske problemer har omfattende litteratur i forbindelse med den seneste tids interesse for disse problemer. Vanskelighederne ved disse problemer ligger i, at løsningerne på problemet skal præsenteres i form af en strategi og dermed et beslutningstræ. Meyniels formodninger er en af de største udfordringer i grafteori.De to hold i konsortiet har ekspertise om disse problemer. — de kan også bestå af problemer, for hvilke verifikationen af løsningen kræver en dynamisk, itereret beregning. Dette er f.eks. tilfældet med problemerne med percolation, skift vagter (evigt dominans) eller magt-dominering til applikationer til elnet. Med hensyn til sidstnævnte er projektinitiativtageren for nylig blevet bedt om at skrive et bogkapitel. (Se ansøgningsdossieret.) (Danish) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: I de dynamiske grafer samfund er der flere tilgange til analysen i gennemsnit: — trinvis algoritmeanalyse: en datastruktur opretholder invariants på den dynamiske graf under dens udvikling det er denkompleksitet i gennemsnit af forespørgsler til denne struktur, der analyseres — Dynamic Erdös-Rényi model: Suppresions og tilføjelser af kanter tegnes tilfældigt på hvert trin i tiden. — begrænset tilfældig model: handlingen af at tilføje eller fjerne kanter besluttes af en modstander, men den modificerede højderyg trækkes tilfældigt. Mange arbejde i analytiske kombinatorier findes omkring den gennemsnitlige analyse af algoritmer, der opererer på statiske grafer mærket (eller ej). For nylig er der arbejde med grafanalyse med begrænsede etiketter (vækst af etiketter undervejs, gentagelse af etiketter). Tilfældig generation: Det aktuelle tekniske niveau er opdelt i tre dele: ad hoc tilfældige generatorer til forskellige applikationer (viære netværk og telekommunikationsnet), mere generiske algoritmer (Boltzmann og Monte-Carlo-metoden) og relativt enkle at simulere tilfældige grafmodeller (Erdös-Rényi, Watts-Strogatz og Barabási). Den første del består af bidrag fra LITIS, den anden er et speciale i Greyc, og den sidste del er velkendt for begge parter. I betragtning af dette fælles sprog ønsker vi at dele vores ekspertise for at forbedre det aktuelle tekniske niveau i begge samfund. Algoritmiske dynamiske grafer: Litteraturen om algoritmer til dynamiske grafer starter generelt fra applikationer og søger at løse et specifikt problem i forbindelse med denne applikation. Referencedokumentet, der indeholder en liste over de forskellige sammenhænge, er Holmes (2015, i de generelle henvisninger). Forskellige problemer er blevet undersøgt ud fra et algoritmisk synspunkt, herunder problemet med den kommercielle rejsende, problemer med bølger, og mere høflighed stier. Der er stadig få bidrag fra konsortiet om emnet, men det er kun projektets mål. Dynamiske problemer på grafer: Dynamiske problemer med grafer er af to slags. — De kan på den ene side være problemer i form af to-player-spil, såsom problemet med gendarmer og tyven, hvor spillet om dominans. Disse klassiske problemer har omfattende litteratur i forbindelse med den seneste tids interesse for disse problemer. Vanskelighederne ved disse problemer ligger i, at løsningerne på problemet skal præsenteres i form af en strategi og dermed et beslutningstræ. Meyniels formodninger er en af de største udfordringer i grafteori.De to hold i konsortiet har ekspertise om disse problemer. — de kan også bestå af problemer, for hvilke verifikationen af løsningen kræver en dynamisk, itereret beregning. Dette er f.eks. tilfældet med problemerne med percolation, skift vagter (evigt dominans) eller magt-dominering til applikationer til elnet. Med hensyn til sidstnævnte er projektinitiativtageren for nylig blevet bedt om at skrive et bogkapitel. (Se ansøgningsdossieret.) (Danish) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
În comunitatea de grafice dinamice există mai multe abordări pentru analiză, în medie: — analiza algoritmilor incrementali: o structură de datemenține invariante pe graficul dinamic în timpul evoluției sale, complexitatea medie a interogărilor la această structură este analizată – modelul dinamic Erdös-Rényi: Supresiunile și adaosurile de margini sunt trase aleatoriu la fiecare etapă a timpului. — model aleatoriu restricționat: acțiunea de adăugare sau îndepărtare a marginilor este decisă de un adversar, dar creasta modificată este trasă aleatoriu. Multe lucrări în combinatorii analitice există în jurul analizei medii a algoritmilor care funcționează pe grafice statice etichetate (sau nu). Mai recent, se lucrează la analiza grafurilor cu etichete limitate (creșterea etichetelor de-a lungul drumului, repetarea etichetelor). Generare aleatorie: Stadiul actual al tehnologiei este împărțit în trei părți: generatoare aleatorii ad-hoc pentru diferite aplicații (rețele vii și rețele de telecomunicații), algoritmi mai generici (metoda Boltzmann și Monte-Carlo) și relativ simplu de simulat modele de grafe aleatorii (Erdös-Rényi, Watts-Strogatz și Barabási). Prima parte constă în contribuții din partea LITIS, a doua este o specialitate Greyc, iar ultima parte este bine cunoscută de ambii parteneri. Având în vedere acest limbaj comun, dorim să împărtășim expertiza noastră pentru a îmbunătăți stadiul actual al tehnologiei în ambele comunități. Grafice dinamice algoritmice: Literatura de specialitate privind algoritmii pentru graficele dinamice pornește, în general, de la aplicații și caută să rezolve o problemă specifică legată de această aplicație. Lucrarea de referință care enumeră diferitele contexte este cea a lui Holmes (2015, în referințele generale). Diverse probleme au fost studiate din punct de vedere algoritmic, inclusiv problema călătorului comercial, problemele valurilor și căile de curtoazie. Există încă puține contribuții din partea consorțiului pe această temă, dar acesta este doar obiectivul proiectului. Probleme dinamice pe grafice: Problemele dinamice cu graficele sunt de două tipuri. Acestea pot fi, pe de o parte, probleme prezentate sub formă de jocuri cu doi jucători, cum ar fi problema jandarmilor și a hoțului, unde jocul dominației. Aceste probleme clasice au o literatură abundentă legată de interesul recent pentru aceste probleme. Dificultatea acestor probleme constă în faptul că soluțiile la această problemă trebuie prezentate sub forma unei strategii și, prin urmare, a unui arbore decizional. Conjectura lui Meyniel este una dintre provocările majore din teoria grafurilor. Cele două echipe ale consorțiului au expertiză în aceste probleme. acestea pot consta, de asemenea, în probleme pentru care verificarea soluției necesită un calcul dinamic și iterat. Acesta este cazul, de exemplu, al problemelor de percolare, de schimbare a gărzilor (dominare eternă) sau de dominare a puterii pentru aplicațiile rețelelor electrice. Pe această din urmă temă, promotorului proiectului i s-a cerut recent să scrie un capitol de carte. (A se vedea dosarul de candidatură.) (Romanian) | |||||||||||||||
| Property / summary: În comunitatea de grafice dinamice există mai multe abordări pentru analiză, în medie: — analiza algoritmilor incrementali: o structură de datemenține invariante pe graficul dinamic în timpul evoluției sale, complexitatea medie a interogărilor la această structură este analizată – modelul dinamic Erdös-Rényi: Supresiunile și adaosurile de margini sunt trase aleatoriu la fiecare etapă a timpului. — model aleatoriu restricționat: acțiunea de adăugare sau îndepărtare a marginilor este decisă de un adversar, dar creasta modificată este trasă aleatoriu. Multe lucrări în combinatorii analitice există în jurul analizei medii a algoritmilor care funcționează pe grafice statice etichetate (sau nu). Mai recent, se lucrează la analiza grafurilor cu etichete limitate (creșterea etichetelor de-a lungul drumului, repetarea etichetelor). Generare aleatorie: Stadiul actual al tehnologiei este împărțit în trei părți: generatoare aleatorii ad-hoc pentru diferite aplicații (rețele vii și rețele de telecomunicații), algoritmi mai generici (metoda Boltzmann și Monte-Carlo) și relativ simplu de simulat modele de grafe aleatorii (Erdös-Rényi, Watts-Strogatz și Barabási). Prima parte constă în contribuții din partea LITIS, a doua este o specialitate Greyc, iar ultima parte este bine cunoscută de ambii parteneri. Având în vedere acest limbaj comun, dorim să împărtășim expertiza noastră pentru a îmbunătăți stadiul actual al tehnologiei în ambele comunități. Grafice dinamice algoritmice: Literatura de specialitate privind algoritmii pentru graficele dinamice pornește, în general, de la aplicații și caută să rezolve o problemă specifică legată de această aplicație. Lucrarea de referință care enumeră diferitele contexte este cea a lui Holmes (2015, în referințele generale). Diverse probleme au fost studiate din punct de vedere algoritmic, inclusiv problema călătorului comercial, problemele valurilor și căile de curtoazie. Există încă puține contribuții din partea consorțiului pe această temă, dar acesta este doar obiectivul proiectului. Probleme dinamice pe grafice: Problemele dinamice cu graficele sunt de două tipuri. Acestea pot fi, pe de o parte, probleme prezentate sub formă de jocuri cu doi jucători, cum ar fi problema jandarmilor și a hoțului, unde jocul dominației. Aceste probleme clasice au o literatură abundentă legată de interesul recent pentru aceste probleme. Dificultatea acestor probleme constă în faptul că soluțiile la această problemă trebuie prezentate sub forma unei strategii și, prin urmare, a unui arbore decizional. Conjectura lui Meyniel este una dintre provocările majore din teoria grafurilor. Cele două echipe ale consorțiului au expertiză în aceste probleme. acestea pot consta, de asemenea, în probleme pentru care verificarea soluției necesită un calcul dinamic și iterat. Acesta este cazul, de exemplu, al problemelor de percolare, de schimbare a gărzilor (dominare eternă) sau de dominare a puterii pentru aplicațiile rețelelor electrice. Pe această din urmă temă, promotorului proiectului i s-a cerut recent să scrie un capitol de carte. (A se vedea dosarul de candidatură.) (Romanian) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: În comunitatea de grafice dinamice există mai multe abordări pentru analiză, în medie: — analiza algoritmilor incrementali: o structură de datemenține invariante pe graficul dinamic în timpul evoluției sale, complexitatea medie a interogărilor la această structură este analizată – modelul dinamic Erdös-Rényi: Supresiunile și adaosurile de margini sunt trase aleatoriu la fiecare etapă a timpului. — model aleatoriu restricționat: acțiunea de adăugare sau îndepărtare a marginilor este decisă de un adversar, dar creasta modificată este trasă aleatoriu. Multe lucrări în combinatorii analitice există în jurul analizei medii a algoritmilor care funcționează pe grafice statice etichetate (sau nu). Mai recent, se lucrează la analiza grafurilor cu etichete limitate (creșterea etichetelor de-a lungul drumului, repetarea etichetelor). Generare aleatorie: Stadiul actual al tehnologiei este împărțit în trei părți: generatoare aleatorii ad-hoc pentru diferite aplicații (rețele vii și rețele de telecomunicații), algoritmi mai generici (metoda Boltzmann și Monte-Carlo) și relativ simplu de simulat modele de grafe aleatorii (Erdös-Rényi, Watts-Strogatz și Barabási). Prima parte constă în contribuții din partea LITIS, a doua este o specialitate Greyc, iar ultima parte este bine cunoscută de ambii parteneri. Având în vedere acest limbaj comun, dorim să împărtășim expertiza noastră pentru a îmbunătăți stadiul actual al tehnologiei în ambele comunități. Grafice dinamice algoritmice: Literatura de specialitate privind algoritmii pentru graficele dinamice pornește, în general, de la aplicații și caută să rezolve o problemă specifică legată de această aplicație. Lucrarea de referință care enumeră diferitele contexte este cea a lui Holmes (2015, în referințele generale). Diverse probleme au fost studiate din punct de vedere algoritmic, inclusiv problema călătorului comercial, problemele valurilor și căile de curtoazie. Există încă puține contribuții din partea consorțiului pe această temă, dar acesta este doar obiectivul proiectului. Probleme dinamice pe grafice: Problemele dinamice cu graficele sunt de două tipuri. Acestea pot fi, pe de o parte, probleme prezentate sub formă de jocuri cu doi jucători, cum ar fi problema jandarmilor și a hoțului, unde jocul dominației. Aceste probleme clasice au o literatură abundentă legată de interesul recent pentru aceste probleme. Dificultatea acestor probleme constă în faptul că soluțiile la această problemă trebuie prezentate sub forma unei strategii și, prin urmare, a unui arbore decizional. Conjectura lui Meyniel este una dintre provocările majore din teoria grafurilor. Cele două echipe ale consorțiului au expertiză în aceste probleme. acestea pot consta, de asemenea, în probleme pentru care verificarea soluției necesită un calcul dinamic și iterat. Acesta este cazul, de exemplu, al problemelor de percolare, de schimbare a gărzilor (dominare eternă) sau de dominare a puterii pentru aplicațiile rețelelor electrice. Pe această din urmă temă, promotorului proiectului i s-a cerut recent să scrie un capitol de carte. (A se vedea dosarul de candidatură.) (Romanian) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / summary | |||||||||||||||
I de dynamiska graferna finns det flera metoder för analysen i genomsnitt: — analys av inkrementell algoritm: en datastrukturbibehåller invarianter på den dynamiska grafen under dess utveckling är detkomplexitet i genomsnitt av frågor till denna struktur som analyseras – Dynamic Erdös-Rényi modell: Suppresions och tillägg av kanter dras slumpmässigt vid varje steg i tiden. — begränsad slumpmässig modell: åtgärden att lägga till eller ta bort kanter avgörs av en motståndare, men den modifierade åsen ritas slumpmässigt. Många arbeten i analytisk kombinatorials finns kring den genomsnittliga analysen av algoritmer som arbetar på statiska grafer märkta (eller inte). På senare tid har man börjat arbeta med grafanalys med begränsade etiketter (tillväxt av etiketter längs vägen, upprepande etiketter). Slumpmässig generering: Den senaste tekniken är indelad i tre delar: tillfälliga slumpgeneratorer för olika tillämpningar (viarnät och telekomnät), mer generiska algoritmer (Boltzmann- och Monte-Carlo-metoden) och relativt enkla att simulera slumpmässiga grafmodeller (Erdös-Rényi, Watts-Strogatz och Barabási). Den första delen består av bidrag från LITIS, den andra är en specialitet av Greyc och den sista delen är välkänd för båda parter. Med tanke på detta gemensamma språk vill vi dela med oss av vår expertis för att förbättra den senaste tekniken i båda samhällena. Algoritmiska dynamiska grafer: Litteraturen om algoritmer för dynamiska grafer utgår i allmänhet från applikationer och syftar till att lösa ett specifikt problem i samband med denna applikation. Referensdokumentet med de olika sammanhangen är Holmes (2015, i de allmänna referenserna). Olika problem har studerats ur algoritmisk synvinkel, bland annat problemet med den kommersiella resenären, problem med vågor och mer artighetsvägar. Det finns fortfarande få bidrag från konsortiet i ämnet, men detta är bara syftet med projektet. Dynamiska problem på grafer: Dynamiska problem med grafer är av två slag. — De kan, å ena sidan, vara problem som presenteras i form av tvåspelarspel, såsom problemet med gendarmer och tjuven, där dominansspelet. Dessa klassiska problem har en riklig litteratur kopplad till den senaste tidens intresse för dessa problem. Svårigheten med dessa problem ligger i att lösningarna på problemet måste presenteras i form av en strategi, alltså ett beslutsträd. Meyniels förmodan är en av de största utmaningarna inom grafteori. De två grupperna i konsortiet har expertis om dessa problem. — de kan också bestå av problem för vilka kontrollen av lösningen kräver en dynamisk, upprepad beräkning. Detta gäller till exempel problemen med perkolering, skiftande vakter (ev. evig dominans) eller maktdominans för tillämpningar till kraftnät. I det senare ämnet ombads projektledaren nyligen att skriva ett bokkapitel. (Se ansökningsakten.) (Swedish) | |||||||||||||||
| Property / summary: I de dynamiska graferna finns det flera metoder för analysen i genomsnitt: — analys av inkrementell algoritm: en datastrukturbibehåller invarianter på den dynamiska grafen under dess utveckling är detkomplexitet i genomsnitt av frågor till denna struktur som analyseras – Dynamic Erdös-Rényi modell: Suppresions och tillägg av kanter dras slumpmässigt vid varje steg i tiden. — begränsad slumpmässig modell: åtgärden att lägga till eller ta bort kanter avgörs av en motståndare, men den modifierade åsen ritas slumpmässigt. Många arbeten i analytisk kombinatorials finns kring den genomsnittliga analysen av algoritmer som arbetar på statiska grafer märkta (eller inte). På senare tid har man börjat arbeta med grafanalys med begränsade etiketter (tillväxt av etiketter längs vägen, upprepande etiketter). Slumpmässig generering: Den senaste tekniken är indelad i tre delar: tillfälliga slumpgeneratorer för olika tillämpningar (viarnät och telekomnät), mer generiska algoritmer (Boltzmann- och Monte-Carlo-metoden) och relativt enkla att simulera slumpmässiga grafmodeller (Erdös-Rényi, Watts-Strogatz och Barabási). Den första delen består av bidrag från LITIS, den andra är en specialitet av Greyc och den sista delen är välkänd för båda parter. Med tanke på detta gemensamma språk vill vi dela med oss av vår expertis för att förbättra den senaste tekniken i båda samhällena. Algoritmiska dynamiska grafer: Litteraturen om algoritmer för dynamiska grafer utgår i allmänhet från applikationer och syftar till att lösa ett specifikt problem i samband med denna applikation. Referensdokumentet med de olika sammanhangen är Holmes (2015, i de allmänna referenserna). Olika problem har studerats ur algoritmisk synvinkel, bland annat problemet med den kommersiella resenären, problem med vågor och mer artighetsvägar. Det finns fortfarande få bidrag från konsortiet i ämnet, men detta är bara syftet med projektet. Dynamiska problem på grafer: Dynamiska problem med grafer är av två slag. — De kan, å ena sidan, vara problem som presenteras i form av tvåspelarspel, såsom problemet med gendarmer och tjuven, där dominansspelet. Dessa klassiska problem har en riklig litteratur kopplad till den senaste tidens intresse för dessa problem. Svårigheten med dessa problem ligger i att lösningarna på problemet måste presenteras i form av en strategi, alltså ett beslutsträd. Meyniels förmodan är en av de största utmaningarna inom grafteori. De två grupperna i konsortiet har expertis om dessa problem. — de kan också bestå av problem för vilka kontrollen av lösningen kräver en dynamisk, upprepad beräkning. Detta gäller till exempel problemen med perkolering, skiftande vakter (ev. evig dominans) eller maktdominans för tillämpningar till kraftnät. I det senare ämnet ombads projektledaren nyligen att skriva ett bokkapitel. (Se ansökningsakten.) (Swedish) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / summary: I de dynamiska graferna finns det flera metoder för analysen i genomsnitt: — analys av inkrementell algoritm: en datastrukturbibehåller invarianter på den dynamiska grafen under dess utveckling är detkomplexitet i genomsnitt av frågor till denna struktur som analyseras – Dynamic Erdös-Rényi modell: Suppresions och tillägg av kanter dras slumpmässigt vid varje steg i tiden. — begränsad slumpmässig modell: åtgärden att lägga till eller ta bort kanter avgörs av en motståndare, men den modifierade åsen ritas slumpmässigt. Många arbeten i analytisk kombinatorials finns kring den genomsnittliga analysen av algoritmer som arbetar på statiska grafer märkta (eller inte). På senare tid har man börjat arbeta med grafanalys med begränsade etiketter (tillväxt av etiketter längs vägen, upprepande etiketter). Slumpmässig generering: Den senaste tekniken är indelad i tre delar: tillfälliga slumpgeneratorer för olika tillämpningar (viarnät och telekomnät), mer generiska algoritmer (Boltzmann- och Monte-Carlo-metoden) och relativt enkla att simulera slumpmässiga grafmodeller (Erdös-Rényi, Watts-Strogatz och Barabási). Den första delen består av bidrag från LITIS, den andra är en specialitet av Greyc och den sista delen är välkänd för båda parter. Med tanke på detta gemensamma språk vill vi dela med oss av vår expertis för att förbättra den senaste tekniken i båda samhällena. Algoritmiska dynamiska grafer: Litteraturen om algoritmer för dynamiska grafer utgår i allmänhet från applikationer och syftar till att lösa ett specifikt problem i samband med denna applikation. Referensdokumentet med de olika sammanhangen är Holmes (2015, i de allmänna referenserna). Olika problem har studerats ur algoritmisk synvinkel, bland annat problemet med den kommersiella resenären, problem med vågor och mer artighetsvägar. Det finns fortfarande få bidrag från konsortiet i ämnet, men detta är bara syftet med projektet. Dynamiska problem på grafer: Dynamiska problem med grafer är av två slag. — De kan, å ena sidan, vara problem som presenteras i form av tvåspelarspel, såsom problemet med gendarmer och tjuven, där dominansspelet. Dessa klassiska problem har en riklig litteratur kopplad till den senaste tidens intresse för dessa problem. Svårigheten med dessa problem ligger i att lösningarna på problemet måste presenteras i form av en strategi, alltså ett beslutsträd. Meyniels förmodan är en av de största utmaningarna inom grafteori. De två grupperna i konsortiet har expertis om dessa problem. — de kan också bestå av problem för vilka kontrollen av lösningen kräver en dynamisk, upprepad beräkning. Detta gäller till exempel problemen med perkolering, skiftande vakter (ev. evig dominans) eller maktdominans för tillämpningar till kraftnät. I det senare ämnet ombads projektledaren nyligen att skriva ett bokkapitel. (Se ansökningsakten.) (Swedish) / qualifier | |||||||||||||||
point in time: 11 August 2022
| |||||||||||||||
| Property / beneficiary | |||||||||||||||
| Property / beneficiary: UNIVERSITE LE HAVRE NORMANDIE / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / beneficiary name (string) | |||||||||||||||
UNIVERSITE LE HAVRE NORMANDIE | |||||||||||||||
| Property / beneficiary name (string): UNIVERSITE LE HAVRE NORMANDIE / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / fund | |||||||||||||||
| Property / fund: European Regional Development Fund / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / postal code | |||||||||||||||
76063 | |||||||||||||||
| Property / postal code: 76063 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / contained in NUTS | |||||||||||||||
| Property / contained in NUTS: Seine-Maritime / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / contained in NUTS: Seine-Maritime / qualifier | |||||||||||||||
| Property / contained in Local Administrative Unit | |||||||||||||||
| Property / contained in Local Administrative Unit: Le Havre / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / contained in Local Administrative Unit: Le Havre / qualifier | |||||||||||||||
| Property / coordinate location | |||||||||||||||
49°29'38.04"N, 0°6'28.69"E
| |||||||||||||||
| Property / coordinate location: 49°29'38.04"N, 0°6'28.69"E / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / coordinate location: 49°29'38.04"N, 0°6'28.69"E / qualifier | |||||||||||||||
| Property / start time | |||||||||||||||
1 January 2021
| |||||||||||||||
| Property / start time: 1 January 2021 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / end time | |||||||||||||||
30 April 2023
| |||||||||||||||
| Property / end time: 30 April 2023 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / date of last update | |||||||||||||||
7 December 2023
| |||||||||||||||
| Property / date of last update: 7 December 2023 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Latest revision as of 02:12, 9 October 2024
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
1 January 2021
0 references
30 April 2023
0 references
UNIVERSITE LE HAVRE NORMANDIE
0 references
76063
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.1523171731679524
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
Dünaamiliste graafikute kogukonnas on analüüsi jaoks keskmiselt mitu lähenemisviisi: – täiendavate algoritmide analüüs: andmestruktuur säilitab dünaamilise graafiku invariants arengu ajal on analüüsitud selle struktuuri kohta keskmiselt päringute tegemise keerukus – Dynamic Erdös-Rényi mudel: Tarned ja täiendused servad on koostatud juhuslikult igal sammul. – piiratud juhumudel: servade lisamise või eemaldamise toimingu otsustab vastane, kuid modifitseeritud servad tõmmatakse juhuslikult. Paljud tööd analüütiline kombinatorials olemas umbes keskmine analüüs algoritmid töötavad staatiline graafikud märgistatud (või mitte). Viimasel ajal on käimas töö graafikute analüüsiga, mis hõlmab piiratud märgiseid (märgiste kasv teel, siltide kordamine). Juhuslik põlvkond: Tehnika tase on jagatud kolme ossa: ad hoc juhuslikud generaatorid erinevate rakenduste jaoks (viraalvõrgud ja telekommunikatsioonivõrgud), üldisemad algoritmid (Boltzmanni ja Monte-Carlo meetod) ning suhteliselt lihtsad juhusliku graafiku mudelid (Erdös-Rényi, Watts-Strogatz ja Barabási). Esimene osa koosneb LITISe panusest, teine Greyci erialast ja viimane osa on mõlemale partnerile hästi teada. Arvestades seda ühist keelt, soovime jagada oma teadmisi, et parandada mõlema kogukonna tehnika taset. Algoritmilised dünaamilised graafikud: Dünaamilise graafiku algoritme käsitlev kirjandus algab üldiselt rakendustest ja püüab lahendada selle rakendusega seotud konkreetset probleemi. Viitedokument, milles on loetletud erinevad kontekstid, on Holmesi oma (2015, üldviidetes). Algoritmilisest vaatepunktist on uuritud erinevaid probleeme, sealhulgas kommertsreisija probleemi, lainete probleeme ja rohkem viisakaid teid. Konsortsium on selles küsimuses veel vähe kaastööd teinud, kuid see on vaid projekti eesmärk. Dünaamilised probleemid graafikutel: Dünaamilised probleemid graafikutega on kahte liiki. – Need võivad ühelt poolt olla kahe mängijaga mängude kujul esitatud probleemid, nagu sandarme ja varas, kus domineerimine toimub. Need klassikalised probleemid on rikkalik kirjandus, mis on seotud hiljutise huviga nende probleemide vastu. Nende probleemide raskus seisneb selles, et probleemi lahendused tuleb esitada strateegia kujul, seega otsustamisskeemina. Meyniel oletuste on üks peamisi väljakutseid graafik teooria.Kaks meeskonda konsortsiumi on teadmisi nende probleemide. – need võivad koosneda ka probleemidest, mille puhul lahenduse kontrollimine nõuab dünaamilist itereeritud arvutust. Nii on see näiteks perkolatsiooni, kaitsepiirete nihutamise (igavene domineerimine) või elektrivõrkudesse tehtavate rakenduste elektridomeenimisega seotud probleemide puhul. Viimati nimetatud teemal paluti projekti elluviijal hiljuti kirjutada raamatupeatükk. (Vt taotlustoimikut.) (Estonian)
11 August 2022
0 references
Dinaminių grafikų bendruomenėje yra keli analizės metodai: – papildomo algoritmo analizė: duomenų struktūra išlaiko kintamuosius dinaminio grafiko metu, tai yra vidutiniškai sudėtingų užklausų į šią struktūrą, kuri yra analizuojama – Dynamic Erdös-Rényi modelis: Suppresions ir papildymai kraštų yra atsitiktine tvarka kiekviename laiko etape. – ribotas atsitiktinis modelis: iš pridedant arba pašalinant kraštų veiksmų nusprendžia priešininkas, bet modifikuota ketera yra sudarytas atsitiktine tvarka. Daug darbo analitinių derinių srityje yra apie vidutinę algoritmų, veikiančių ant statinių grafikų (arba ne), analizę. Pastaruoju metu pradedamas darbas grafiko analizės srityje, naudojant suvaržytas etiketes (ženklų augimas pakeliui, etikečių kartojimas). Atsitiktinė generacija: Naujausias technikos lygis suskirstytas į tris dalis: ad hoc atsitiktiniai generatoriai įvairioms reikmėms (viariniai tinklai ir telekomunikacijų tinklai), bendresni algoritmai (Boltzmann ir Monte-Carlo metodas) ir palyginti paprasti atsitiktinių grafikų modeliai (Erdös-Rényi, Watts-Strogatz ir Barabįsi). Pirmąją dalį sudaro LITIS įnašai, antroji – Greyc specialybė, o paskutinė dalis gerai žinoma abiem partneriams. Atsižvelgdami į šią bendrą kalbą, norime pasidalinti savo patirtimi, kad būtų pagerintas abiejų bendruomenių modernumas. Algoritminiai dinaminiai grafikai: Literatūra apie dinaminių grafikų algoritmus paprastai prasideda nuo taikomųjų programų ir ja siekiama išspręsti konkrečią su šia programa susijusią problemą. Informacinis dokumentas, kuriame išvardijami skirtingi kontekstai, yra Holmes (2015 m. bendrosiose nuorodose). Algoritminiu požiūriu buvo ištirtos įvairios problemos, įskaitant komercinio keliautojo problemą, bangų problemas ir daugiau mandagumo takų. Šiuo klausimu konsorciumas vis dar mažai prisidėjo, tačiau tai yra tik projekto tikslas. Dinaminės problemos diagramose: Dinaminės problemos su grafikais yra dviejų rūšių. – Jie gali būti, viena vertus, problemų, pateiktų dviejų žaidėjų žaidimų forma, pavyzdžiui, žandarmų ir vagio problema, kur dominavimo žaidimas. Šios klasikinės problemos turi gausybę literatūros, susijusios su pastarojo meto susidomėjimu šiomis problemomis. Šių problemų sudėtingumas susijęs su tuo, kad problemos sprendimai turi būti pateikti strategijos, taigi ir sprendimų medžio, forma. Meyniel hipotezė yra vienas iš pagrindinių iššūkių grafikos teorijoje. Dvi konsorciumo komandos turi žinių apie šias problemas. – jie taip pat gali būti susiję su problemomis, kurių sprendimui patikrinti reikalingas dinaminis kartotinis skaičiavimas. Taip yra, pavyzdžiui, dėl prasiskverbimo, apsaugų perkėlimo (amžinojo dominavimo) ar elektros energijos dominavimo į elektros tinklus. Pastaruoju metu projekto rengėjo buvo paprašyta parašyti knygos skyrių. (Žr. paraiškos bylą.) (Lithuanian)
11 August 2022
0 references
U zajednici s dinamičkim grafikonima postoji nekoliko pristupa za analizu u prosjeku: — inkrementalna analiza algoritma: struktura podataka zadržava invarijante na dinamičkom grafikonu tijekom njegove evolucije, analizirana je složenost u prosjeku upita za tu strukturu – dinamički Erdös-Rényi model: Suppresions i dodaci rubova su nacrtani nasumično u svakom koraku vremena. — ograničeni slučajni model: djelovanje dodavanja ili uklanjanja rubova odlučuje protivnik, ali modificirani greben je nacrtan nasumce. Mnogi rade u analitičkim kombinatorima oko prosječne analize algoritama koji rade na statičkim grafovima označenim (ili ne). U novije vrijeme pojavljuje se rad na analizi grafikona s ograničenim oznakama (rast oznaka na putu, ponavljanje oznaka). Nasumična generacija: Stanje tehnike podijeljeno je na tri dijela: ad hoc nasumični generatori za različite primjene (mreže za ptice i telekomunikacijske mreže), općenitiji algoritmi (metoda Boltzmann i Monte-Carlo) i relativno jednostavni za simulaciju nasumičnih grafičkih modela (Erdös-Rényi, Watts-Strogatz i Barabási). Prvi dio se sastoji od doprinosa iz LITIS, drugi je specijalnost Greyc i posljednji dio je dobro poznat oba partnera. S obzirom na taj zajednički jezik želimo podijeliti svoje stručno znanje kako bismo poboljšali najnovija dostignuća u objema zajednicama. Algoritamski dinamički grafikoni: Literatura o algoritmima za dinamičke grafove općenito počinje od aplikacija i nastoji riješiti određeni problem povezan s ovom aplikacijom. Referentni dokument u kojem su navedeni različiti konteksti nalazi se u Holmesu (2015., u općim referencama). Proučavani su različiti problemi s algoritamskog stajališta, uključujući problem komercijalnog putnika, probleme valova i više ljubaznosti. Još uvijek postoji malo doprinosa konzorcija o toj temi, ali to je samo cilj projekta. Dinamički problemi na grafikonima: Dinamički problemi sa grafovima su dvije vrste. — Oni mogu biti, s jedne strane, problemi predstavljeni u obliku dva igrača igre, kao što je problem žandarmes i lopov, gdje igra dominacije. Ovi klasični problemi imaju bogatu literaturu povezanu s nedavnim interesom za oveprobleme. Poteškoće tih problema leži u činjenici da rješenja problema moraju biti predstavljena u obliku strategije, a time i stabla odlučivanja. Meyniel je pretpostavka je jedan od glavnih izazova u teorija graf.The dva tima konzorcija imaju stručnost o tim problemima. — mogu se sastojati i od problema za koje provjera rješenja zahtijeva dinamičan, iterirani izračun. To je, na primjer, slučaj s problemima perkolacije, pomicanja čuvara (vječne dominacije) ili dominacije energije za primjene u elektroenergetskim mrežama. Na potonju temu, promotor projekta nedavno je zamoljen da napiše poglavlje knjige. (Vidjeti datoteku zahtjeva.) (Croatian)
11 August 2022
0 references
Στη δυναμική κοινότητα γραφημάτων υπάρχουν διάφορες προσεγγίσεις για την ανάλυση κατά μέσο όρο: — αυξητική ανάλυση αλγορίθμων: μια δομή δεδομένωνδιατηρεί αναλλοίωτους στο δυναμικό γράφημα κατά τη διάρκεια της εξέλιξής του είναι η πολυπλοκότητα κατά μέσο όρο των ερωτημάτων σε αυτή τη δομή που αναλύεται — Dynamic Erdös-Rényi model: Οι Suppresions και οι προσθήκες των άκρων σχεδιάζονται τυχαία σε κάθε στάδιο του χρόνου. — περιορισμένο τυχαίο μοντέλο: η δράση της προσθήκης ή της αφαίρεσης των άκρων αποφασίζεται από έναν αντίπαλο, αλλά η τροποποιημένη κορυφογραμμή σχεδιάζεται τυχαία. Πολλές εργασίες στους αναλυτικούς συνδυασμούς υπάρχουν γύρω από τη μέση ανάλυση αλγορίθμων που λειτουργούν σε στατικά γραφήματα με επισήμανση (ή όχι). Πιο πρόσφατα, αναδύονται εργασίες για την ανάλυση γραφημάτων με περιορισμένες ετικέτες (ανάπτυξη ετικετών κατά μήκος της διαδρομής, επανάληψη ετικετών). Τυχαία γενιά: Η εξέλιξη της τεχνολογίας διαιρείται σε τρία μέρη: ad-hoc τυχαίες γεννήτριες για διαφορετικές εφαρμογές (δίκτυα κηπευτικών και τηλεπικοινωνιακά δίκτυα), πιο γενικοί αλγόριθμοι (μέθοδος Boltzmann και Monte-Carlo) και σχετικά απλοί στην προσομοίωση μοντέλων τυχαίων γραφημάτων (Erdös-Rényi, Watts-Strogatz και Barabási). Το πρώτο μέρος αποτελείται από συνεισφορές της LITIS, το δεύτερο είναι μια ειδικότητα της Greyc και το τελευταίο είναι γνωστό και στους δύο εταίρους. Δεδομένης αυτής της κοινής γλώσσας, θέλουμε να μοιραστούμε την εμπειρογνωσία μας για τη βελτίωση της τεχνολογίας και στις δύο κοινότητες. Αλγοριθμικές δυναμικές γραφικές παραστάσεις: Η βιβλιογραφία σχετικά με τους αλγορίθμους για δυναμικά γραφήματα γενικά ξεκινά από εφαρμογές και επιδιώκει να λύσει ένα συγκεκριμένο πρόβλημα που σχετίζεται με αυτή την εφαρμογή. Το έγγραφο αναφοράς που απαριθμεί τα διαφορετικά πλαίσια είναι εκείνο του Holmes (2015, στις γενικές παραπομπές). Διάφορα προβλήματα έχουν μελετηθεί από αλγοριθμική άποψη, συμπεριλαμβανομένου του προβλήματος του εμπορικού ταξιδιώτη, προβλήματα των κυμάτων, και πιο ευγένεια μονοπάτια. Υπάρχουν ακόμη λίγες συνεισφορές από την κοινοπραξία σχετικά με το θέμα, αλλά αυτός είναι μόνο ο στόχος του έργου. Δυναμικά προβλήματα στα γραφήματα: Τα δυναμικά προβλήματα με τα γραφήματα είναι δύο ειδών. — Μπορούν να είναι, αφενός, προβλήματα που παρουσιάζονται με τη μορφή παιχνιδιών δύο παικτών, όπως το πρόβλημα των χωροφυλάκων και του κλέφτη, όπου το παιχνίδι της κυριαρχίας. Αυτά τα κλασικά προβλήματα έχουν άφθονη λογοτεχνία που συνδέεται με το πρόσφατο ενδιαφέρον για αυτά τα προβλήματα. Η δυσκολία αυτών των προβλημάτων έγκειται στο γεγονός ότι οι λύσεις στο πρόβλημα πρέπει να παρουσιάζονται με τη μορφή μιας στρατηγικής, εξ ου και ενός δέντρου αποφάσεων. Η εικασία του Meyniel είναι μία από τις μεγαλύτερες προκλήσεις στη θεωρία γραφημάτων. Οι δύο ομάδες της κοινοπραξίας έχουν εμπειρογνωμοσύνη σε αυτά τα προβλήματα. — μπορούν επίσης να συνίστανται σε προβλήματα για τα οποία η επαλήθευση της λύσης απαιτεί δυναμικό και επαναλαμβανόμενο υπολογισμό. Αυτό συμβαίνει, για παράδειγμα, με τα προβλήματα της διήθησης, της μετατόπισης φρουρών (αιώνια κυριαρχία) ή της κυριαρχίας ενέργειας για εφαρμογές σε δίκτυα ηλεκτρικής ενέργειας. Σχετικά με το τελευταίο θέμα, ο φορέας υλοποίησης του έργου κλήθηκε πρόσφατα να γράψει ένα κεφάλαιο για το βιβλίο. (Βλ. φάκελο αίτησης.) (Greek)
11 August 2022
0 references
V komunite dynamických grafov existuje v priemere niekoľko prístupov k analýze: — analýza prírastkových algoritmov: dátová štruktúrazachováva invarianty na dynamickom grafe počas jeho vývoja je to komplexnosť v priemere dotazov na túto štruktúru, ktorá sa analyzuje – Dynamic Erdös-Rényi model: Suppresions a prírastky okrajov sú vykreslené náhodne v každom kroku času. — obmedzený náhodný model: o pridaní alebo odstránení hrán rozhoduje súper, ale upravený hrebeň je vykreslený náhodne. Veľa práce v analytických kombinátoroch existuje okolo priemernej analýzy algoritmov fungujúcich na statických grafoch označených (alebo nie). Nedávno sa pracuje na analýze grafov s obmedzenými štítkami (rozmnožovanie štítkov pozdĺž cesty, opakovanie štítkov). Náhodné generovanie: Stav techniky je rozdelený na tri časti: ad-hoc náhodné generátory pre rôzne aplikácie (viary a telekomunikačné siete), všeobecnejšie algoritmy (Boltzmann a Monte-Carlo metóda) a relatívne jednoduché simulovať modely náhodných grafov (Erdös-Rényi, Watts-Strogatz a Barabási). Prvá časť pozostáva z príspevkov z LITIS, druhá je špecializácia Greyc a posledná časť je dobre známa obom partnerom. Vzhľadom na tento spoločný jazyk sa chceme podeliť o naše odborné znalosti s cieľom zlepšiť stav techniky v oboch komunitách. Algoritmické dynamické grafy: Literatúra o algoritmoch dynamických grafov vo všeobecnosti začína od aplikácií a snaží sa vyriešiť konkrétny problém súvisiaci s touto aplikáciou. Referenčný dokument, v ktorom sa uvádzajú rôzne súvislosti, je dokument Holmes (2015, vo všeobecných odkazoch). Z algoritmického hľadiska sa skúmali rôzne problémy vrátane problému komerčného cestujúceho, problémov s vlnami a zdvorilejších ciest. Na túto tému je stále málo príspevkov konzorcia, ale to je len cieľ projektu. Dynamické problémy na grafoch: Dynamické problémy s grafmi sú dvoch druhov. — Môžu byť, na jednej strane, problémy prezentované vo forme dvojhrových hier, ako je problém žandárov a zlodeja, kde hra nadvlády. Tieto klasické problémy majú bohatú literatúru spojenú s nedávnym záujmom o tieto problémy. Ťažkosti týchto problémov spočívajú v tom, že riešenia tohto problému musia byť prezentované vo forme stratégie, teda v podobe rozhodovacieho stromu. Meynielova domnienka je jednou z hlavných výziev v teórii grafu. Dva tímy konzorcia majú odborné znalosti o týchto problémoch. — môžu pozostávať aj z problémov, pri ktorých si overenie riešenia vyžaduje dynamický, iterovaný výpočet. Je to tak napríklad v prípade problémov s perkoláciou, posunom strážcov (večná nadvláda) alebo prevahou moci pre aplikácie do elektrických rozvodných sietí. Pokiaľ ide o druhú tému, organizátor projektu bol nedávno požiadaný, aby napísal kapitolu knihy. (Pozri súbor žiadosti.) (Slovak)
11 August 2022
0 references
Dynaamisessa kaavioyhteisössä on useita lähestymistapoja analyysiin keskimäärin: — asteittainen algoritmianalyysi: tietorakenne ylläpitää invariantteja dynaamisessa kaaviossa sen evoluution aikana, se on tämän rakenteen kyselyiden keskimäärin monimutkaisuus, joka analysoidaan – Dynamic Erdös-Rényi -malli: Suppresions ja lisäykset reunat piirretään satunnaisesti kussakin vaiheessa aikaa. — rajoitettu satunnainen malli: vastustaja päättää reunojen lisäämisestä tai poistamisesta, mutta muokattu harjanteen piirretään satunnaisesti. Monet työt analyyttisten combinatorials on noin keskimääräinen analyysi algoritmeja toimivat staattisia kaavioita merkitty (tai ei). Viime aikoina on kehittymässä grafiikka-analyysejä, joissa on rajoitettuja merkintöjä (etikettien kasvu matkan varrella, tarrojen toistaminen). Satunnainen sukupolvi: Uusinta tekniikkaa on jaettu kolmeen osaan: satunnaiset satunnaisgeneraattorit eri sovelluksiin (viaariverkot ja televiestintäverkot), yleisempiä algoritmeja (Boltzmannin ja Monte-Carlon menetelmä) ja suhteellisen yksinkertaisia simuloida satunnaisia kaaviomalleja (Erdös-Rényi, Watts-Strogatz ja Barabási). Ensimmäinen osa koostuu LITIS:n maksuosuuksista, toinen on Greycin erikoisuus ja viimeinen osa on hyvin molempien osapuolten tiedossa. Tämän yhteisen kielen vuoksi haluamme jakaa asiantuntemustamme molempien yhteisöjen huipputason parantamiseksi. Algoritmidynaamiset kaaviot: Dynaamisten kaavioiden algoritmeja koskeva kirjallisuus alkaa yleensä sovelluksista ja pyrkii ratkaisemaan tähän sovellukseen liittyvän erityisongelman. Viiteasiakirja, jossa luetellaan eri asiayhteydet, on Holmesin viiteasiakirja (2015, yleisissä viittauksissa). Algoritmista näkökulmasta on tutkittu erilaisia ongelmia, kuten kaupallisen matkustajan ongelma, aaltojen ongelmat ja kohteliaisuuspolut. Konsortiolta on vielä vain vähän asiaa koskevia kannanottoja, mutta tämä on vain hankkeen tavoite. Dynaamiset ongelmat kaavioissa: Dynaamiset ongelmat kaavioissa ovat kahdenlaisia. — Ne voivat olla, toisaalta, ongelmia esitetään muodossa kahden pelaajan pelejä, kuten ongelma santarmit ja varas, jossa peli dominaatio. Nämä klassiset ongelmat ovat runsaasti kirjallisuutta, joka liittyy viimeaikaiseen kiinnostukseen näitä ongelmia kohtaan. Näiden ongelmien vaikeus on se, että ongelman ratkaisut on esitettävä strategiana, eli päätöksentekopuuna. Meyniel arveluihin on yksi suurimmista haasteista kaavioteoria.Kahdella joukkueella on asiantuntemusta näistä ongelmista. — ne voivat muodostua myös ongelmista, joiden osalta ratkaisun todentaminen edellyttää dynaamista, itioitua laskentaa. Tämä koskee esimerkiksi suojusta, suojusten vaihtamista (ikuinen ylivalta) tai sähköverkkoihin liittyvien sovellusten virranhallintaa. Jälkimmäisen aiheen osalta hankkeen toteuttajaa pyydettiin äskettäin kirjoittamaan kirjan luku. (Ks. hakemustiedosto.) (Finnish)
11 August 2022
0 references
W środowisku dynamicznych wykresów istnieje średnio kilka podejść do analizy: — przyrostowa analiza algorytmów: struktura danych utrzymuje niezmienność na wykresie dynamicznym podczas jego ewolucji, jest to skomplikowanie średnio zapytań do tej struktury, która jest analizowana – model Dynamic Erdös-Rényi: Supresje i dodatki krawędzi są rysowane losowo na każdym kroku czasu. — ograniczony model losowy: o akcji dodawania lub usuwania krawędzi decyduje przeciwnik, ale zmodyfikowany grzbiet jest losowo rysowany. Wiele prac w kombinatorach analitycznych istnieje wokół średniej analizy algorytmów działających na wykresach statycznych oznakowanych (lub nie). Ostatnio pojawiają się prace nad analizą wykresów z ograniczonymi etykietami (wzrost etykiet po drodze, powtarzanie etykiet). Generowanie losowe: Stan techniki dzieli się na trzy części: generatory losowe ad hoc do różnych zastosowań (sieci voary i sieci telekomunikacyjne), bardziej ogólne algorytmy (metoda Boltzmann i Monte-Carlo) oraz stosunkowo proste do symulacji losowych modeli wykresów (Erdös-Rényi, Watts-Strogatz i Barabási). Pierwsza część składa się z wkładów LITIS, druga to specjalność Greyc, a ostatnia część jest dobrze znana obu partnerom. Biorąc pod uwagę ten wspólny język, chcemy dzielić się naszą wiedzą fachową w celu poprawy stanu techniki w obu społecznościach. Algorytmiczne wykresy dynamiczne: Literatura na temat algorytmów wykresów dynamicznych zazwyczaj zaczyna się od aplikacji i ma na celu rozwiązanie konkretnego problemu związanego z tą aplikacją. Dokument referencyjny, w którym wymieniono różne konteksty, dotyczy Holmesa (2015 r., w odniesieniach ogólnych). Z algorytmicznego punktu widzenia przeanalizowano różne problemy, w tym problem podróżnika komercyjnego, problemy fal i bardziej uprzejmości. Konsorcjum wciąż ma niewiele wkładów na ten temat, ale jest to tylko cel projektu. Dynamiczne problemy na wykresach: Dynamiczne problemy z wykresami są dwa rodzaje. — Mogą to być, z jednej strony, problemy prezentowane w postaci gier dla dwóch graczy, takich jak problem żandarmów i złodzieja, gdzie gra dominacji. Te klasyczne problemy mają obszerną literaturę związaną z niedawnym zainteresowaniem tymi problemami. Trudność tych problemów polega na tym, że rozwiązania problemu muszą być przedstawione w formie strategii, a zatem schematu decyzyjnego. Przypuszczenie Meyniela jest jednym z głównych wyzwań w teorii wykresów. Oba zespoły konsorcjum mają wiedzę na temat tych problemów. — mogą one również składać się z problemów, w przypadku których weryfikacja rozwiązania wymaga dynamicznego, wieloetapowego obliczenia. Dzieje się tak na przykład w przypadku problemów perkolacji, przesuwania osłon (wieczna dominacja) lub dominacji mocy dla zastosowań w sieciach energetycznych. Na ten ostatni temat promotor projektu został niedawno poproszony o napisanie rozdziału książki. (Patrz plik wniosku.) (Polish)
11 August 2022
0 references
A dinamikus gráfok közösségében átlagosan több megközelítés létezik: – növekményes algoritmuselemzés: az adatstruktúra evolúciója során invariánsokat tart fenn a dinamikus gráfon, átlagosan az elemzett struktúrára vonatkozó lekérdezések összetettsége – Dynamic Erdös-Rényi modell: A készleteket és az élek hozzáadását véletlenszerűen kell rajzolni az idő minden egyes lépésénél. – korlátozott véletlenszerű modell: az élek hozzáadásának vagy eltávolításának műveletét az ellenfél dönti el, de a módosított gerincet véletlenszerűen rajzolják. Analitikus kombinációkban sok munka létezik a statikus gráfokon (vagy nem) jelölt (vagy nem) grafikákon működő algoritmusok átlagelemzése körül. A közelmúltban a gráfelemzéssel kapcsolatos munka korlátozott címkékkel (a címkék növekedése útközben, a címkék megismétlése) kapcsolatos munka alakul ki. Véletlenszerű generáció: A technika állása három részre oszlik: ad-hoc véletlenszerű generátorok különböző alkalmazásokhoz (viárius hálózatok és távközlési hálózatok), általánosabb algoritmusok (Boltzmann és Monte-Carlo módszer) és viszonylag egyszerű szimulálni véletlenszerű gráfmodelleket (Erdös-Rényi, Watts-Strogatz és Barabási). Az első rész a LITIS hozzájárulásaiból áll, a második Greyc specialitása, az utolsó rész pedig mindkét fél számára jól ismert. Tekintettel erre a közös nyelvre, szeretnénk megosztani szakértelmünket annak érdekében, hogy mindkét közösség korszerűbbé váljon. Algoritmikus dinamikus gráfok: A dinamikus gráfok algoritmusairól szóló szakirodalom általában alkalmazásokból indul ki, és az alkalmazással kapcsolatos konkrét probléma megoldására törekszik. A különböző összefüggéseket felsoroló referenciadokumentum Holmesé (2015, az általános hivatkozásokban). Különböző problémákat vizsgáltunk algoritmikus szempontból, beleértve a kereskedelmi utazó problémáját, a hullámok problémáit és az udvariasabb utakat. Még mindig kevés a konzorcium hozzájárulása a témában, de ez csak a projekt célja. Dinamikus problémák a grafikonokon: A gráfokkal kapcsolatos dinamikus problémák kétféleek. – Ezek lehetnek, egyrészt a problémák bemutatott formájában kétjátékos játékok, mint például a probléma a csendőrség és a tolvaj, ahol a játék az uralom. Ezeknek a klasszikus problémáknak bőséges szakirodaloma van, ami az utóbbi időben e problémák iránti érdeklődéshez kapcsolódik. E problémák nehézsége abban rejlik, hogy a probléma megoldását stratégiában, azaz döntési fában kell bemutatni. Meyniel sejtése az egyik legnagyobb kihívás a grafikonelméletben.A konzorcium két csapata szakértelemmel rendelkezik ezekkel a problémákkal kapcsolatban. – olyan problémák is lehetnek, amelyek esetében a megoldás ellenőrzése dinamikus, iterált számítást igényel. Ez a helyzet például a perkoláció, a védőburkolatok elmozdítása (örök dominancia) vagy az erőátviteli rendszer alkalmazásai esetében. Az utóbbi témában a projektgazdát a közelmúltban felkérték, hogy írjon könyvfejezetet. (Lásd a kérelemfájlt.) (Hungarian)
11 August 2022
0 references
V komunitě dynamických grafů existuje v průměru několik přístupů k analýze: — inkrementální analýza algoritmů: struktura dat udržuje invarianty na dynamickém grafu během jeho vývoje je to složitost v průměru dotazů na tuto strukturu, která je analyzována – Dynamic Erdös-Rényi model: Suppresions a přírůstky hran jsou vykresleny náhodně v každém kroku času. — omezený náhodný model: o akci přidávání nebo odstraňování hran rozhoduje soupeř, ale upravený hřeben je nakreslen náhodně. Mnoho prací v analytických kombinátorech existuje kolem průměrné analýzy algoritmů pracujících na statických grafech označených (nebo ne). V poslední době se objevuje práce na analýze grafů s omezenými štítky (růst štítků podél cesty, opakování štítků). Náhodné generování: Stav techniky je rozdělen do tří částí: ad hoc generátory pro různé aplikace (viární sítě a telekomunikační sítě), obecnější algoritmy (metoda Boltzmann a Monte-Carlo) a relativně jednoduché simulace modelů náhodných grafů (Erdös-Rényi, Watts-Strogatz a Barabási). První část se skládá z příspěvků LITIS, druhá je specialitou Greyc a poslední část je dobře známá oběma partnerům. Vzhledem k tomuto společnému jazyku chceme sdílet své odborné znalosti, abychom zlepšili stav techniky v obou komunitách. Algoritmické dynamické grafy: Literatura o algoritmech pro dynamické grafy obvykle začíná od aplikací a snaží se vyřešit konkrétní problém související s touto aplikací. Referenční dokument, v němž jsou uvedeny různé souvislosti, je kontext Holmes (2015, v obecných odkazech). Z algoritmického hlediska byly zkoumány různé problémy, včetně problému komerčního cestovatele, problémů vln a zdvořilějších cest. Stále existuje jen málo příspěvků konsorcia na toto téma, ale to je jen cíl projektu. Dynamické problémy na grafech: Dynamické problémy s grafy jsou dvou druhů. — Mohou být, na jedné straně, problémy prezentovány ve formě dvou hráčů hry, jako je problém četníků a zloděj, kde hra o nadvládu. Tyto klasické problémy mají bohatou literaturu spojenou s nedávným zájmem o tyto problémy. Obtížnost těchto problémů spočívá v tom, že řešení tohoto problému musí být prezentována ve formě strategie, tedy rozhodovacího stromu. Meyniel domněnka je jedním z hlavních výzev v teorii grafů.Dva týmy konsorcia mají odborné znalosti o těchto problémech. — mohou také spočívat v problémech, pro které ověření řešení vyžaduje dynamický, iterovaný výpočet. Tak je tomu například v případě problémů s perkolací, řazením ochranných krytů (věčná nadvláda) nebo dominací energie pro aplikace do rozvodných sítí. Pokud jde o posledně uvedené téma, předkladatel projektu byl nedávno požádán, aby napsal kapitolu knihy. (Viz soubor žádosti.) (Czech)
11 August 2022
0 references
Dinamisko diagrammu kopienai ir vairākas pieejas analīzei vidēji: — inkrementālā algoritma analīze: datu struktūra uztur mainīgos elementus dinamiskajā grafikā tās evolūcijas laikā tā ir šīs struktūras vaicājumu sarežģītība, kas tiek analizēta — Dynamic Erdös-Rényi modelis: Suppresions un papildinājumi malām tiek sastādīti nejauši katrā laika posmā. — ierobežota nejaušības principa modelis: malu pievienošanas vai noņemšanas darbību izlemj pretinieks, bet modificētā kores tiek izvilkta nejauši. Daudzi darbi analītiskajās kombinatorijās pastāv ap to algoritmu vidējo analīzi, kas darbojas ar statiskajām diagrammām (vai ne). Pēdējā laikā notiek darbs pie grafikas analīzes ar ierobežotām etiķetēm (marķējumu augšana pa ceļam, etiķešu atkārtošana). Nejaušā ģenerēšana: Jaunākie sasniegumi ir sadalīti trīs daļās: ad hoc nejauši ģeneratori dažādiem lietojumiem (vijo tīkli un telekomunikāciju tīkli), vispārīgāki algoritmi (Boltzmann un Monte-Carlo metode) un salīdzinoši vienkārši modelējami nejaušu grafiku modeļi (Erdös-Rényi, Watts-Strogatz un Barabási). Pirmā daļa sastāv no LITIS iemaksām, otrā ir Greyc specialitāte, un pēdējā daļa ir labi zināma abiem partneriem. Ņemot vērā šo kopīgo valodu, mēs vēlamies dalīties pieredzē, lai uzlabotu jaunākos sasniegumus abās kopienās. Algoritmiskie dinamiskie grafiki: Literatūra par dinamisko grafiku algoritmiem parasti sākas no lietojumprogrammām un cenšas atrisināt konkrētu problēmu, kas saistīta ar šo lietojumprogrammu. Atsauces dokuments, kurā uzskaitīti dažādie konteksti, ir Holmes (2015. gads, vispārīgajās atsaucēs). No algoritmiskā viedokļa ir pētītas dažādas problēmas, tostarp komerciālā ceļotāja problēma, viļņu problēmas un vairāk pieklājīgu ceļu. Konsorcijs par šo jautājumu joprojām sniedz maz ieguldījumu, bet tas ir tikai projekta mērķis. Dinamiskās problēmas grafikos: Dinamiskās problēmas ar grafikiem ir divu veidu. — Tie var būt, no vienas puses, problēmas, kas iesniegtas kā divu spēlētāju spēles, piemēram, problēma žandarmiem un zaglis, kur spēle dominēšanu. Šīs klasiskās problēmas ir bagātas literatūrā, kas saistīta ar neseno interesi par šiemproblēmām. Šo problēmu sarežģī fakts, ka problēmas risinājumi ir jāsniedz stratēģijas veidā, tātad — lēmumu pieņemšanas shēmā. Meyniel pieņēmumi ir viens no galvenajiem izaicinājumiem graph teorijā. Abām konsorcija komandām ir zināšanas par šīm problēmām. — tās var ietvert arī problēmas, kuru dēļ risinājuma pārbaudei ir vajadzīgs dinamisks un atkārtots aprēķins. Tas attiecas, piemēram, uz problēmām, kas saistītas ar perkolāciju, aizsargu maiņu (mūžīgā dominēšana) vai elektroenerģijas domināciju izmantošanai elektrotīklos. Par pēdējo minēto tematu projekta virzītājs nesen tika aicināts uzrakstīt grāmatu nodaļu. (Skatīt pieteikuma datni.) (Latvian)
11 August 2022
0 references
Sna graif dhinimiciúla tá roinnt cur chuige ann don anailís ar an meán: — anailís incriminteach algartam: struchtúr sonraí Coinníonn invariants ar an graf dinimiciúil le linn a éabhlóide go bhfuil sé thecomplexity ar an meán na n-iarratas ar an struchtúr a bhfuil anailís déanta — Dynamic Erdös-Rényi samhail: Déantar soláthairtí agus breiseanna imill a tharraingt go randamach ag gach céim den am. — samhail randamach theoranta: is é an comhraic a chinneann an gníomh a bhaineann le himill a chur leis nó a bhaint ach tarraingítear an iomaire modhnaithe go randamach. Tá go leor oibre i gcombinatorials anailíseacha thart ar an meán anailís ar algartaim ag feidhmiú ar graif statacha lipéadaithe (nó nach bhfuil). Le déanaí, tá obair ag teacht chun cinn ar anailís graf le lipéid shrianta (fás lipéad feadh na slí, lipéid athdhéanta). Giniúint randamach: Tá staid na healaíne roinnte ina thrí chuid: gineadóirí randamacha ad-hoc d’iarratais éagsúla (líonraíviacha agus líonraí teileachumarsáide), algartaim níos cineálaí (modh Boltzmann agus Monte-Carlo) agus réasúnta simplí samhlacha graf randamach a ionsamhlú (Erdös-Rényi, Watts-Strogatz agus Barabási). Is éard atá sa chéad chuid ná aighneachtaí ó litis, is speisialtacht GREYC an dara ceann agus tá an chuid dheireanach ar eolas go maith ag an dá chomhpháirtí. I bhfianaise na teanga coitinne seo, ba mhaith linn ár saineolas a roinnt chun feabhas a chur ar an úrscothacht sa dá phobal. Graif dhinimiciúla algartamacha: Tosaíonn an litríocht ar algartaim le haghaidh graif dhinimiciúla go ginearálta ó iarratais agus féachann sé le fadhb shonrach a bhaineann leis an iarratas seo a réiteach. Is é an páipéar tagartha a liostú na comhthéacsanna éagsúla sin de Holmes (2015, sna tagairtí ginearálta). Fadhbanna éagsúla a ndearnadh staidéar orthu ó thaobh algartamach de, lena n-áirítear an fhadhb an lucht siúil tráchtála, fadhbanna na dtonnta, agus cosáin cúirtéise níos mó. Níl mórán rannchuidithe fós ón gcuibhreannas ar an ábhar, ach níl ansin ach cuspóir an tionscadail. Fadhbanna dinimiciúla ar ghraif: Tá dhá chineál fadhbanna dinimiciúla le graif. — Is féidir leo a bheith, ar thaobh amháin, fadhbanna i láthair i bhfoirm cluichí dhá-imreoir, mar shampla an fhadhb gendarmes agus an thief, i gcás an cluiche de forlámhas. Tá na fadhbanna clasaiceach litríocht flúirseach nasctha leis an spéis le déanaí sna fadhbanna seo. Is é an deacracht a bhaineann leis na fadhbanna seo ná go gcaithfear na réitigh ar an bhfadhb a chur i láthair i bhfoirm straitéise, dá bhrí sin crann cinnteoireachta. Tá tuairim Meyniel ar cheann de na dúshláin is mó i graf teoiric.Tá an dá fhoireann an cuibhreannas saineolas ar na fadhbanna seo. — d’fhéadfadh fadhbanna a bheith i gceist leo freisin a dteastaíonn ríomh dinimiciúil, atrialáilte ina leith chun an réiteach a fhíorú. Is amhlaidh atá, mar shampla, leis na fadhbanna a bhaineann le síothlú, gardaí aistrithe (forlámhas seachtrach) nó forlámhas cumhachta d’iarratais ar ghreillí cumhachta. Ar an ábhar deireanach sin, iarradh ar thionscnóir an tionscadail le déanaí caibidil leabhar a scríobh. (Féach an comhad iarratais.) (Irish)
11 August 2022
0 references
V dinamičnih grafih skupnost obstaja več pristopov za analizo v povprečju: — analiza dodatnega algoritma: struktura podatkov ohranja invariante na dinamičnem grafu med njegovim razvojem je kompleksnost v povprečju poizvedb v tej strukturi, ki se analizira – Dynamic Erdös-Rényi model: Suppresioni in dodatki robov se naključno narišejo na vsakem koraku. — omejeni naključni model: dejanje dodajanja ali odstranjevanja robov odloča nasprotnik, vendar je spremenjeni greben sestavljen naključno. Veliko dela v analitičnih kombinatorjih obstaja okoli povprečne analize algoritmov, ki delujejo na statičnih grafih, označenih (ali ne). V zadnjem času se začenja delo v zvezi z analizo grafov z omejenimi oznakami (rast oznak na poti, ponavljanje oznak). Naključna generacija: Stanje tehnike je razdeljeno na tri dele: ad-hoc naključni generatorji za različne aplikacije (viarska omrežja in telekomunikacijska omrežja), bolj generični algoritmi (metoda Boltzmann in Monte-Carlo) in razmeroma preprosti za simulacijo naključnih grafov (Erdös-Rényi, Watts-Strogatz in Barabási). Prvi del sestavljajo prispevki LITIS, drugi je posebnost Greyca, zadnji del pa je dobro znan obema partnerjema. Glede na ta skupni jezik želimo deliti svoje strokovno znanje za izboljšanje stanja tehnike v obeh skupnostih. Algoritemski dinamični grafi: Literatura o algoritmih za dinamične grafe se običajno začne z aplikacijami in skuša rešiti specifičen problem, povezan s to aplikacijo. Referenčni dokument, v katerem so navedeni različni konteksti, je dokument družbe Holmes (2015, v splošnih referencah). Z algoritemskega vidika so bili preučeni različni problemi, vključno s problemom komercialnega potnika, problemi valov in bolj vljudnostnimi potmi. Še vedno je malo prispevkov konzorcija na to temo, vendar je to samo cilj projekta. Dinamične težave na grafih: Dinamične težave z grafi so dveh vrst. — Po eni strani so lahko problemi, predstavljeni v obliki dvoigralskih iger, kot je problem žandarmov in tatu, kjer je igra dominacije. Ti klasični problemi imajo bogato literaturo, povezano z nedavnim zanimanjem za te težave. Težava teh težav je v tem, da morajo biti rešitve problema predstavljene v obliki strategije, s tem pa tudi v obliki drevesa odločanja. Meynielova domneva je eden od glavnih izzivov v teoriji grafov. Dve ekipi konzorcija imata strokovno znanje o teh težavah. — lahko so sestavljeni tudi iz težav, za katere preverjanje rešitve zahteva dinamičen, iteriran izračun. To velja na primer pri problemih perkolacije, premikanja varoval (večna dominacija) ali dominacije moči za aplikacije v električna omrežja. V zvezi s slednjim je bil predlagatelj projekta pred kratkim pozvan, naj napiše poglavje o knjigi. (Glej prijavno dokumentacijo.) (Slovenian)
11 August 2022
0 references
В динамичните графики общността има няколко подхода за анализ средно: — поетапен анализ на алгоритъма: структура на даннитеподдържа invariants на динамичната графика по време на еволюцията му е сложността на средно заявки към тази структура, която се анализира — Dynamic Erdös-Rényi модел: Suppresions и допълнения на ръбове се чертаят на случаен принцип на всеки етап от времето. — ограничен произволен модел: действието на добавяне или премахване на ръбове се определя от противник, но модифицираната хребета се чертае на случаен принцип. Много работа в аналитичните комбинаториуми съществува около средния анализ на алгоритми, работещи на статични графики, етикетирани (или не). В последно време започва работа по графичен анализ с ограничени етикети (растеж на етикетите по пътя, повтаряне на етикетите). Произволно генериране: Състоянието на техниката е разделено на три части: ad-hoc случайни генератори за различни приложения (волиарни мрежи и телекомуникационни мрежи), по-общи алгоритми (метод на Болцман и Монте Карло) и сравнително прости за симулиране на случайни графични модели (Erdös-Rényi, Watts-Strogatz и Barabási). Първата част се състои от принос на LITIS, втората е специалност на Грейк, а последната е добре позната на двамата партньори. Като се има предвид този общ език, искаме да споделим нашия експертен опит за подобряване на състоянието на технологиите и в двете общности. Алгоритмични динамични графики: Литературата за алгоритмите за динамични графики обикновено започва от приложения и се стреми да реши конкретен проблем, свързан с това приложение. Референтният документ, в който се изброяват различните контексти, е този на Холмс (2015 г., в общите препратки). От алгоритмична гледна точка са проучени различни проблеми, включително проблема с търговския пътник, проблемите на вълните и по-учтивите пътища. Все още има малко мнения от консорциума по този въпрос, но това е само целта на проекта. Динамични проблеми на графиките: Динамичните проблеми с графиките са от два вида. — Те могат да бъдат, от една страна, проблеми, представени под формата на игри с двама играчи, като проблема с жандармите и крадеца, където играта на господство. Тези класически проблеми имат богата литература, свързана с неотдавнашния интерес към тези проблеми. Трудността на тези проблеми се състои във факта, че решенията на проблема трябва да бъдат представени под формата на стратегия, следователно дърво на решенията. Meyniel "и предположения е един от основните предизвикателства в графика теория.Двете екипи на консорциума имат опит по тези проблеми. — те могат да се състоят и от проблеми, за които проверката на решението изисква динамично, итерирано изчисление. Такъв е случаят например с проблемите с перколацията, изместването на предпазителите (вечно господство) или доминирането на мощността за приложения към електропреносните мрежи. По последния въпрос организаторът на проекта наскоро беше помолен да напише глава от книгата. (Вж. досието на заявлението.) (Bulgarian)
11 August 2022
0 references
Fil-komunità tal-graffs dinamiċi hemm diversi approċċi għall-analiżi bħala medja: — analiżi inkrimentali algoritmu: struttura tad-data żżomm invarjanti fuq il-graff dinamika matul l-evoluzzjoni tagħha hija l-kumplessità fuq medja ta ‘mistoqsijiet għal din l-istruttura li hija analizzata — mudell Dynamic Erdös-Rényi: Suppresions u żidiet ta ‘truf huma mfassla saltwarjament f’kull pass ta’ ħin. — mudell aleatorju ristrett: l-azzjoni ta ‘żieda jew tneħħija truf huwa deċiż minn avversarju iżda l-pont modifikat huwa mfassal b’mod aleatorju. Ħafna xogħol fil-kombinazzjonijiet analitiċi jeżisti madwar l-analiżi medja ta ‘algoritmi li joperaw fuq graffs statiċi tikkettati (jew le). Aktar reċentement, qed toħroġ ħidma fuq l-analiżi tal-graff b’tikketti limitati (tkabbir ta’ tikketti tul it-triq, tikketti ripetuti). Ġenerazzjoni każwali: L-istat tal-arti huwa maqsum fi tliet partijiet: ġeneraturi każwali ad hoc għal applikazzjonijiet differenti (netwerks vjarji u netwerks tat-telekomunikazzjoni), algoritmi aktar ġeneriċi (metodu Boltzmann u Monte-Carlo) u relattivament sempliċi biex jissimulaw mudelli ta’ graff każwali (Erdös-Rényi, Watts-Strogatz u Barabási). L-ewwel parti tikkonsisti f’kontribuzzjonijiet minn LITIS, it-tieni hija speċjalità ta’ Greyc u l-aħħar parti hija magħrufa sew għaż-żewġ imsieħba. Minħabba din il-lingwa komuni, irridu naqsmu l-għarfien espert tagħna biex intejbu l-istat tal-arti fiż-żewġ komunitajiet. Graffs dinamiċi algoritmiċi: Il-letteratura dwar l-algoritmi għall-graffs dinamiċi ġeneralment tibda mill-applikazzjonijiet u tfittex li ssolvi problema speċifika relatata ma’ din l-applikazzjoni. Id-dokument ta’ referenza li jelenka l-kuntesti differenti huwa dak ta’ Holmes (2015, fir-referenzi ġenerali). Diversi problemi ġew studjati mill-perspettiva algoritmika, inkluża l-problema tal-vjaġġatur kummerċjali, problemi ta’ mewġ, u mogħdijiet aktar ta’ korteżija. Għad hemm ftit kontribuzzjonijiet mill-konsorzju dwar is-suġġett, iżda dan huwa biss l-objettiv tal-proġett. Problemi dinamiċi fuq il-graffs: Problemi dinamiċi bil-graffs huma ta ‘żewġ tipi. — Dawn jistgħu jkunu, minn naħa waħda, problemi ppreżentati fil-forma ta ‘logħob two-player, bħall-problema ta’ gendarmes u l-ħalliel, fejn il-logħba ta ‘dominazzjoni. Dawn il-problemi klassiċi għandhom ħafna letteratura marbuta ma’ l-interess reċenti f’dawn il-problemi. Id-diffikultà ta’ dawn il-problemi tinsab fil-fatt li s-soluzzjonijiet għall-problema jridu jiġu ppreżentati fil-forma ta’ strateġija, u għalhekk dijagramma tad-deċiżjonijiet. Konġettura Meyniel hija waħda mill-isfidi ewlenin fit-teorija graff. Iż-żewġ timijiet tal-konsorzju għandhom kompetenza dwar dawn il-problemi. — dawn jistgħu jikkonsistu wkoll fi problemi li għalihom il-verifika tas-soluzzjoni teħtieġ kalkolu dinamiku u iterat. Dan huwa l-każ, pereżempju, bil-problemi ta ‘perkolazzjoni, ċaqliq ta’ lqugħ (dominazzjoni eterna) jew power-domination għall-applikazzjonijiet għall-grids tal-enerġija. Dwar dan l-aħħar suġġett, il-promotur tal-proġett kien reċentement mitlub jikteb kapitolu tal-ktieb. (Ara l-fajl tal-applikazzjoni.) (Maltese)
11 August 2022
0 references
Na comunidade de gráficos dinâmicos há várias abordagens para a análise em média: — análise de algoritmos incrementais: uma estrutura de dados mantém invariantes no gráfico dinâmico durante a sua evolução é a complexidade média das consultas a esta estrutura que é analisada — modelo dinâmico de Erdös-Rényi: Supressões e adições de bordas são desenhadas aleatoriamente a cada passo do tempo. — modelo aleatório restrito: a ação de adicionar ou remover arestas é decidida por um oponente, mas a crista modificada é desenhada aleatoriamente. Muitos trabalhos em combinatória analítica existem em torno da análise média de algoritmos operando em grafos estáticos rotulados (ou não). Mais recentemente, está a emergir trabalho na análise de gráficos com etiquetas restritas (crescimento de etiquetas ao longo do caminho, repetição de etiquetas). Geração aleatória: O estado da arte divide-se em três partes: geradores aleatórios ad hoc para diferentes aplicações (redes viárias e redes de telecomunicações), algoritmos mais genéricos (método de Boltzmann e Monte-Carlo) e modelos de grafos aleatórios relativamente simples de simular (Erdös-Rényi, Watts-Strogatz e Barabási). A primeira parte é composta por contribuições da LITIS, a segunda é uma especialidade da GREYC e a última parte é bem conhecida por ambos os parceiros. Dada esta linguagem comum, queremos partilhar a nossa experiência para melhorar o estado da arte em ambas as comunidades. Gráficos dinâmicos algorítmicos: A literatura sobre algoritmos para grafos dinâmicos geralmente parte de aplicações e procura resolver um problema específico relacionado a esta aplicação. O artigo de referência que enumera os diferentes contextos é o de Holmes (2015, nas referências gerais). Vários problemas foram estudados do ponto de vista algorítmico, incluindo o problema do viajante comercial, problemas de ondas e caminhos mais corteses. Ainda há poucas contribuições do consórcio sobre o assunto, mas este é apenas o objetivo do projeto. Problemas dinâmicos em gráficos: Problemas dinâmicos com gráficos são de dois tipos. — Podem ser, por um lado, problemas apresentados sob a forma de jogos para dois jogadores, como o problema dos gendarmes e do ladrão, em que o jogo de dominação. Estes problemas clássicos têm abundante literatura ligada ao recente interesse por estesproblemas. A dificuldade destes problemas reside no facto de as soluções para o problema deverem ser apresentadas sob a forma de uma estratégia, daí uma árvore de decisão. A conjectura de Meyniel é um dos principais desafios da teoria dos grafos. As duas equipas do consórcio têm conhecimentos especializados sobre estes problemas. — podem também consistir em problemas para os quais a verificação da solução exige um cálculo dinâmico e iterado. É o caso, por exemplo, dos problemas de percolação, deslocamento de guardas (dominação eterna) ou dominação de poder para aplicações em redes elétricas. Sobre este último tema, o promotor do projeto foi recentemente convidado a escrever um capítulo de livro. (Ver processo de candidatura.) (Portuguese)
11 August 2022
0 references
I de dynamiske grafer samfund er der flere tilgange til analysen i gennemsnit: — trinvis algoritmeanalyse: en datastruktur opretholder invariants på den dynamiske graf under dens udvikling det er denkompleksitet i gennemsnit af forespørgsler til denne struktur, der analyseres — Dynamic Erdös-Rényi model: Suppresions og tilføjelser af kanter tegnes tilfældigt på hvert trin i tiden. — begrænset tilfældig model: handlingen af at tilføje eller fjerne kanter besluttes af en modstander, men den modificerede højderyg trækkes tilfældigt. Mange arbejde i analytiske kombinatorier findes omkring den gennemsnitlige analyse af algoritmer, der opererer på statiske grafer mærket (eller ej). For nylig er der arbejde med grafanalyse med begrænsede etiketter (vækst af etiketter undervejs, gentagelse af etiketter). Tilfældig generation: Det aktuelle tekniske niveau er opdelt i tre dele: ad hoc tilfældige generatorer til forskellige applikationer (viære netværk og telekommunikationsnet), mere generiske algoritmer (Boltzmann og Monte-Carlo-metoden) og relativt enkle at simulere tilfældige grafmodeller (Erdös-Rényi, Watts-Strogatz og Barabási). Den første del består af bidrag fra LITIS, den anden er et speciale i Greyc, og den sidste del er velkendt for begge parter. I betragtning af dette fælles sprog ønsker vi at dele vores ekspertise for at forbedre det aktuelle tekniske niveau i begge samfund. Algoritmiske dynamiske grafer: Litteraturen om algoritmer til dynamiske grafer starter generelt fra applikationer og søger at løse et specifikt problem i forbindelse med denne applikation. Referencedokumentet, der indeholder en liste over de forskellige sammenhænge, er Holmes (2015, i de generelle henvisninger). Forskellige problemer er blevet undersøgt ud fra et algoritmisk synspunkt, herunder problemet med den kommercielle rejsende, problemer med bølger, og mere høflighed stier. Der er stadig få bidrag fra konsortiet om emnet, men det er kun projektets mål. Dynamiske problemer på grafer: Dynamiske problemer med grafer er af to slags. — De kan på den ene side være problemer i form af to-player-spil, såsom problemet med gendarmer og tyven, hvor spillet om dominans. Disse klassiske problemer har omfattende litteratur i forbindelse med den seneste tids interesse for disse problemer. Vanskelighederne ved disse problemer ligger i, at løsningerne på problemet skal præsenteres i form af en strategi og dermed et beslutningstræ. Meyniels formodninger er en af de største udfordringer i grafteori.De to hold i konsortiet har ekspertise om disse problemer. — de kan også bestå af problemer, for hvilke verifikationen af løsningen kræver en dynamisk, itereret beregning. Dette er f.eks. tilfældet med problemerne med percolation, skift vagter (evigt dominans) eller magt-dominering til applikationer til elnet. Med hensyn til sidstnævnte er projektinitiativtageren for nylig blevet bedt om at skrive et bogkapitel. (Se ansøgningsdossieret.) (Danish)
11 August 2022
0 references
În comunitatea de grafice dinamice există mai multe abordări pentru analiză, în medie: — analiza algoritmilor incrementali: o structură de datemenține invariante pe graficul dinamic în timpul evoluției sale, complexitatea medie a interogărilor la această structură este analizată – modelul dinamic Erdös-Rényi: Supresiunile și adaosurile de margini sunt trase aleatoriu la fiecare etapă a timpului. — model aleatoriu restricționat: acțiunea de adăugare sau îndepărtare a marginilor este decisă de un adversar, dar creasta modificată este trasă aleatoriu. Multe lucrări în combinatorii analitice există în jurul analizei medii a algoritmilor care funcționează pe grafice statice etichetate (sau nu). Mai recent, se lucrează la analiza grafurilor cu etichete limitate (creșterea etichetelor de-a lungul drumului, repetarea etichetelor). Generare aleatorie: Stadiul actual al tehnologiei este împărțit în trei părți: generatoare aleatorii ad-hoc pentru diferite aplicații (rețele vii și rețele de telecomunicații), algoritmi mai generici (metoda Boltzmann și Monte-Carlo) și relativ simplu de simulat modele de grafe aleatorii (Erdös-Rényi, Watts-Strogatz și Barabási). Prima parte constă în contribuții din partea LITIS, a doua este o specialitate Greyc, iar ultima parte este bine cunoscută de ambii parteneri. Având în vedere acest limbaj comun, dorim să împărtășim expertiza noastră pentru a îmbunătăți stadiul actual al tehnologiei în ambele comunități. Grafice dinamice algoritmice: Literatura de specialitate privind algoritmii pentru graficele dinamice pornește, în general, de la aplicații și caută să rezolve o problemă specifică legată de această aplicație. Lucrarea de referință care enumeră diferitele contexte este cea a lui Holmes (2015, în referințele generale). Diverse probleme au fost studiate din punct de vedere algoritmic, inclusiv problema călătorului comercial, problemele valurilor și căile de curtoazie. Există încă puține contribuții din partea consorțiului pe această temă, dar acesta este doar obiectivul proiectului. Probleme dinamice pe grafice: Problemele dinamice cu graficele sunt de două tipuri. Acestea pot fi, pe de o parte, probleme prezentate sub formă de jocuri cu doi jucători, cum ar fi problema jandarmilor și a hoțului, unde jocul dominației. Aceste probleme clasice au o literatură abundentă legată de interesul recent pentru aceste probleme. Dificultatea acestor probleme constă în faptul că soluțiile la această problemă trebuie prezentate sub forma unei strategii și, prin urmare, a unui arbore decizional. Conjectura lui Meyniel este una dintre provocările majore din teoria grafurilor. Cele două echipe ale consorțiului au expertiză în aceste probleme. acestea pot consta, de asemenea, în probleme pentru care verificarea soluției necesită un calcul dinamic și iterat. Acesta este cazul, de exemplu, al problemelor de percolare, de schimbare a gărzilor (dominare eternă) sau de dominare a puterii pentru aplicațiile rețelelor electrice. Pe această din urmă temă, promotorului proiectului i s-a cerut recent să scrie un capitol de carte. (A se vedea dosarul de candidatură.) (Romanian)
11 August 2022
0 references
I de dynamiska graferna finns det flera metoder för analysen i genomsnitt: — analys av inkrementell algoritm: en datastrukturbibehåller invarianter på den dynamiska grafen under dess utveckling är detkomplexitet i genomsnitt av frågor till denna struktur som analyseras – Dynamic Erdös-Rényi modell: Suppresions och tillägg av kanter dras slumpmässigt vid varje steg i tiden. — begränsad slumpmässig modell: åtgärden att lägga till eller ta bort kanter avgörs av en motståndare, men den modifierade åsen ritas slumpmässigt. Många arbeten i analytisk kombinatorials finns kring den genomsnittliga analysen av algoritmer som arbetar på statiska grafer märkta (eller inte). På senare tid har man börjat arbeta med grafanalys med begränsade etiketter (tillväxt av etiketter längs vägen, upprepande etiketter). Slumpmässig generering: Den senaste tekniken är indelad i tre delar: tillfälliga slumpgeneratorer för olika tillämpningar (viarnät och telekomnät), mer generiska algoritmer (Boltzmann- och Monte-Carlo-metoden) och relativt enkla att simulera slumpmässiga grafmodeller (Erdös-Rényi, Watts-Strogatz och Barabási). Den första delen består av bidrag från LITIS, den andra är en specialitet av Greyc och den sista delen är välkänd för båda parter. Med tanke på detta gemensamma språk vill vi dela med oss av vår expertis för att förbättra den senaste tekniken i båda samhällena. Algoritmiska dynamiska grafer: Litteraturen om algoritmer för dynamiska grafer utgår i allmänhet från applikationer och syftar till att lösa ett specifikt problem i samband med denna applikation. Referensdokumentet med de olika sammanhangen är Holmes (2015, i de allmänna referenserna). Olika problem har studerats ur algoritmisk synvinkel, bland annat problemet med den kommersiella resenären, problem med vågor och mer artighetsvägar. Det finns fortfarande få bidrag från konsortiet i ämnet, men detta är bara syftet med projektet. Dynamiska problem på grafer: Dynamiska problem med grafer är av två slag. — De kan, å ena sidan, vara problem som presenteras i form av tvåspelarspel, såsom problemet med gendarmer och tjuven, där dominansspelet. Dessa klassiska problem har en riklig litteratur kopplad till den senaste tidens intresse för dessa problem. Svårigheten med dessa problem ligger i att lösningarna på problemet måste presenteras i form av en strategi, alltså ett beslutsträd. Meyniels förmodan är en av de största utmaningarna inom grafteori. De två grupperna i konsortiet har expertis om dessa problem. — de kan också bestå av problem för vilka kontrollen av lösningen kräver en dynamisk, upprepad beräkning. Detta gäller till exempel problemen med perkolering, skiftande vakter (ev. evig dominans) eller maktdominans för tillämpningar till kraftnät. I det senare ämnet ombads projektledaren nyligen att skriva ett bokkapitel. (Se ansökningsakten.) (Swedish)
11 August 2022
0 references
7 December 2023
0 references
Identifiers
20E06110
0 references