Platzeffiziente Graphalgorithmen 2
Zusammenfassung der Projektergebnisse
Graphen kommen in vielen Anwendungen vor, von sozialen Netzwerken bis hin zu Transport und Logistik. Häufig werden diese Graphen aus riesigen Datensätzen erstellt, die als Big Data bezeichnet werden. Da die Anwendungen mit immer größeren Datenmengen konfrontiert werden, wurden Lösungen aus verschiedensten Richtungen entwickelt. Eine dieser Forschungsrichtungen sind die so genannten platzeffizienten Algorithmen, die für ein bestimmtes Problem darauf abzielen, die Laufzeit von Standardlösungen beizubehalten und gleichzeitig den Speicherbedarf erheblich zu reduzieren, was in der Regel bedeutet, dass eine lineare Anzahl von Bits verwendet wird. Dies wird durch die Beobachtung motiviert, dass Algorithmen, die eine sublineare Menge an Speicherplatz verwenden, zu enormen Laufzeiten tendieren, zusammen mit einer unteren Schranke von Barnes et al. [1998], dass gerichtete s-t-Konnektivität in bestimmten Modellen nicht in polynomieller Zeit mit o(n/ √log n) Bits gelöst werden kann. Vor dem Forschungsprojekt waren nur wenige platzeeffiziente Algorithmen bekannt, zum Beispiel für platzeffiziente Varianten von Tiefen- und Breitensuche. Diese genannten platzeffizienten Algorithmen verwenden eine lineare Anzahl von Bits, während sie die optimale lineare Laufzeit (fast) beibehalten. Das Projekt hat die Toolbox für platzeffiziente Algorithmen um mächtige Frameworks erweitert, wie zum Beispiel Algorithmen für die Konstruktion so genannter Baumzerlegungen, eine Struktur, die häufig beim Entwurf parametrisierter Algorithmen für NP-schwere Probleme verwendet wird. Andere Ergebnisse umfassen Algorithmen für spezielle Klassen von Graphen wie planare Graphen und Graphen, die durch sogenannte verbotene Minoren kategorisiert werden können. Ein solches Ergebnis ist ein sogenanntes Graph-Coarsening-Framework, das es ermöglicht, verschiedene Algorithmen platzeffizient auszuführen, mit einem leichten Verlust in der Lösungsqualität. Die Ergebnisse des Projekts umfassen nicht nur statische Graphen, sondern auch dynamische. Erstens für die Konstruktion effizienter und succincter Datenstrukturen, die sogenannte Minor-Operationen (Knotenlöschung sowie das Löschen/Zusammenziehen von Kanten) in planaren Graphen bereitstellen. Minor-Operationen sind in zahlreichen Anwendungen nützlich. Mit Hilfe des oben erwähnten Graph-Coarsening Frameworks kann die genannte Datenstruktur platzeffizient konstruiert werden. Zweitens, platzeffiziente Ergebnisse für sogenannte Explorations- und Multi-Stage-Probleme auf temporalen Graphen, das heißt auf Graphen bei denen sich die Menge der Kanten über diskrete Zeitschritte ändert. Für praktische Anwendungen wurden mit Hilfe von platzeffizienten Strategien ein erfolgreicher Solver für die PACE-Challenge 2024 entworfen, der eine obere Schranke für den Parameter der so genannten Twinwidth berechnet, sowie verschiedene platzeffiziente Algorithmen und Datenstrukturen in einer Bibliothek implementiert.
Link zum Abschlussbericht
https://doi.org/10.34657/17574
Projektbezogene Publikationen (Auswahl)
-
Extra space during initialization of succinct data structures and dynamical initializable arrays. In Proc. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 65:1–65:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Andrej Sajenko
-
Simple 2f -color choice dictionaries. In Proc. 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of LIPIcs, pages 66:1–66:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Andrej Sajenko
-
Space efficient (graph) algorithms. 2018
Frank Kammer & Andrej Sajenko
-
Linear-Time In-Place DFS and BFS on the Word RAM. Lecture Notes in Computer Science, 286-298. Springer International Publishing.
Kammer, Frank & Sajenko, Andrej
-
Two moves per time step make a difference. In Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of LIPIcs, pages 141:1–141:14.
Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko & Jakob T. Spooner
-
Multistage graph problems on a global budget. Theoretical Computer Science, 868, 46-64.
Heeger, Klaus; Himmel, Anne-Sophie; Kammer, Frank; Niedermeier, Rolf; Renken, Malte & Sajenko, Andrej
-
Space-efficient graph coarsening with applications to succinct planar encodings. In Proc. 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of LIPIcs, pages 62:1–62:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Johannes Meintrup
-
Space-Efficient Vertex Separators for Treewidth. Algorithmica, 84(9), 2414-2461.
Kammer, Frank; Meintrup, Johannes & Sajenko, Andrej
-
Open problems in (hyper)graph decomposition, 2023
Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, George Karypis, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani ... & Albert-Jan Yzelman
-
Pace solver description: Exact (guthmi) and heuristic (guthm). In Proc. 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), volume 285 of LIPIcs, pages 37:1–37:7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer & Manuel Penschuck
-
Recent trends in graph decomposition (dagstuhl seminar 23331). Dagstuhl Reports, 13(8):1–45
George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael R. Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer ... & Albert-Jan Yzelman
-
Sorting and Ranking of Self-Delimiting Numbers with Applications to Tree Isomorphism. Lecture Notes in Computer Science, 356-367. Springer Nature Switzerland.
Kammer, Frank; Meintrup, Johannes & Sajenko, Andrej
-
Star: Library for space- and timeefficient algorithms. 2023
Nina Hammer, Frank Kammer & Johannes Meintrup
-
Succinct planar encoding with minor operations. In Proc. 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of LIPIcs, pages 44:1–44:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Johannes Meintrup
-
Exploiting automorphisms of temporal graphs for fast exploration and rendezvous. In Proc. 51st International Colloquium on Automata, Languages, and Programming, (ICALP 2024), volume 297 of LIPIcs, pages 55:1–55:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup & William K. Moses Jr.
-
Space-Efficient Graph Kernelizations. Lecture Notes in Computer Science, 260-271. Springer Nature Singapore.
Kammer, Frank & Sajenko, Andrej
