https://www.dagstuhl.de/22461

13. – 18. November 2022, Dagstuhl-Seminar 22461

Dynamic Graph Algorithms

Organisatoren

Aaron Bernstein (Rutgers University – New Brunswick, US)
Shiri Chechik (Tel Aviv University, IL)
Sebastian Forster (Universität Salzburg, AT)
Tsvi Kopelowitz (Bar-Ilan University – Ramat Gan, IL)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Susanne Bach-Bernhard zu administrativen Fragen

Marsha Kleinbauer zu wissenschaftlichen Fragen

Dagstuhl Reports

Wir bitten die Teilnehmer uns bei der notwendigen Dokumentation zu unterstützen und Abstracts zu ihrem Vortrag, Ergebnisse aus Arbeitsgruppen, etc. zur Veröffentlichung in unserer Serie Dagstuhl Reports einzureichen über unser
Dagstuhl Reports Submission System.

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl-Seminar Wiki
Programm des Dagstuhl-Seminars [pdf]

(Zum Einloggen bitte persönliche DOOR-Zugangsdaten verwenden)

Motivation

The field of dynamic graph algorithms studies algorithms for processing graphs that are changing over time. Formally, the goal is to process an interleaved sequence of update and query operations, where an update operation changes the input graph (e.g. inserts/deletes an edge), while the query operation is problem-specific and asks for some property of the current graph – for example, an s-t path, or a minimum spanning tree. The field has evolved rapidly over the past decade, and this Dagstuhl Seminar will bring together leading researchers in dynamic algorithms and related areas of graph algorithms. Some specific goals for the seminar are outlined below.

  • Because the field has grown so much in recent years, one of the main motivations for this seminar is to establish the main challenges that remain – both a list of specific open problems that continue to resist progress, as well as a discussion of more general limitations to our current upper and lower bound techniques. The seminar will also provide a venue for the community to actively shape the direction of the field going forward.
  • Much of the recent progress in the field has stemmed from a new set of techniques, many of which originated in other areas of graph or approximation algorithms. One of the goals of this seminar is thus to discuss how recent developments in graph algorithms broadly construed can be applied to the dynamic setting in particular, and to disseminate some of the recent techniques that have already had tremendous success in this regard. To this end, we will organize several tutorials from top experts in the field.
  • The experimental evaluation of dynamic graph algorithms is still in its infancy. There are no established data sets or even evaluation methodologies. This seminar aims to include the leading researchers in the area of algorithms engineering of dynamic graph algorithms to address and, hopefully, resolve these fundamental questions.

Motivation text license
  Creative Commons BY 4.0
  Aaron Bernstein, Shiri Chechik, Sebastian Forster, and Tsvi Kopelowitz

Classification

  • Data Structures And Algorithms

Keywords

  • Graph algorithms
  • Dynamic graphs

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.