TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 27031

Graph Algorithms: Making Theoretical Breakthroughs Practical

( 17. Jan – 22. Jan, 2027 )

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/27031

Organisatoren
  • Jakub Lacki (Google - New York, US)
  • Danupon Nanongkai (MPI für Informatik - Saarbrücken, DE)
  • Christian Schulz (Universität Heidelberg, DE)
  • Blair D. Sullivan (University of Utah - Salt Lake City, US)

Kontakt

Motivation

Recent years have been exceptionally fruitful for graph algorithms, yielding major theoretical advancements for fundamental problems like maximum flow, matching, and single-source shortest paths. Despite this progress, a significant gap persists between the asymptotic efficiency of these novel algorithms and their practical utility. Many of these breakthroughs, while theoretically powerful, are either too complex to implement reliably or are hindered by large constant factors and sub-polynomial terms hidden within their complexity analysis. For example, an algorithm with O(n log10 n) complexity, while asymptotically superior to one with O(n2) running time, is likely outperformed for any practical input size.

This Dagstuhl Seminar directly addresses this theory-practice gap by exploring an alternative approach to algorithm design—one that integrates practical considerations from the very beginning. The goal is to bring together algorithm researchers, algorithm engineers, and practitioners to foster a holistic perspective on algorithm development. We aim to create a forum where theorists can present concepts ripe for implementation and where engineers can highlight real-world bottlenecks that require new theoretical insights.

The seminar’s core topics will cover the entire lifecycle of practical algorithm development. Discussions will center on:

  • Design Principles: Moving beyond pure asymptotic analysis to consider metrics like implementation simplicity, low constant factors, and amenability to modern hardware architectures, including cache efficiency and parallelizability.
  • Implementation Strategies: Addressing the challenges of translating complex theoretical constructs into robust, high-performance code, and exploring best practices for optimization and debugging.
  • Evaluation Methodologies: Establishing rigorous standards for empirical analysis and benchmarking to enable fair comparisons and a clear understanding of an algorithm's true performance characteristics.

By facilitating exchange between different communities, this Dagstuhl Seminar aims to accelerate the creation of the next generation of truly practical and impactful graph algorithms.

Copyright Jakub Lacki, Danupon Nanongkai, Christian Schulz, and Blair D. Sullivan

Klassifikation
  • Data Structures and Algorithms

Schlagworte
  • graph algorithms
  • efficient implementation
  • practical algorithms
  • theory of graph algorithms
  • algorithm engineering