Our group tackles a broad spectrum of scalable graph algorithms in particular in the context of very large inputs. In general, our research is based on five pillars: multilevel algorithms, practical kernelization, parallelization, memetic algorithms and dynamic graph algorithms that are highly interconnected. To this end, our group engineers algorithms that improve known methods. Typically, we release the techniques and algorithms developed as easy-to-use open source software. Examples include a widely used library of algorithms for graph partitioning, graph drawing, (weighted) independent sets, hypergraph partitioning, graph clustering, graph generation, minimum cuts, process mapping and many more.

News

    31.08.2024: Three papers of our group have been accepted at the Algorithm Engineering and Experiments (ALENEX) 2025 conference. The first one, Optimal Neighborhood Exploration for Dynamic Independent Sets by Jannick Borowitz, Ernestine Großmann, and Christian Schulz. The second paper, Engineering Fully Dynamic Exact Δ-Orientation Algorithms by Ernestine Großmann, Henrik Reinstädtler, Christian Schulz, and Fabian Walliser. The third paper, Scalable Multilevel and Memetic Signed Graph Clustering by Marcelo Fonseca Faraj, Felix Hausberger, and Christian Schulz.

    14.8.2024: We released a new technical report on "Engineering Algorithms for Hypergraph b-Matching". This is the work of Ernestine Großmann, Felix Joos, Henrik Reinstädtler, and Christian Schulz. You can find the preprint here.

    28.7.2024: The student Team HeiCross secured the 6th place in the student ranking of the PACE Challenge 2024 Heuristic Track (link to results). The team is composed out of Shai Dorian Peretz, Alvaro Garmendia Navarro, Tomer Haham, Antonie Wagner and Marlon Dittes and have been supervised by Adil Chhabra, Ernestine Grossmann, Henrik Reinstädtler, Henning Woydt.

    26.7.2024: Our DFG project proposal "Engineering Advanced (Hyper)graph b-matching Algorithms" has been accepted.

    17.7.2024: We released a new technical report on "Engineering Fully Dynamic Exact Δ-Orientation Algorithms". This is the work of Ernestine Großmann, Henrik Reinstädtler, Christian Schulz and Fabian Walliser. You can find the preprint here.

    10.7.2024: We released a new technical report on "Optimal Neighborhood Exploration for Dynamic Independent Sets". This is the work of Jannick Borowitz, Ernestine Großmann and Christian Schulz. You can find the preprint here.

    9.7.2024: We added a group picture to our team site! Have a look!

    23.6.2024: Two papers of our group have been accepted at the European Symposium on Algorithms. The first one is "Engineering Edge Orientation Algorithms" together with Henrik Reinstädtler, Christian Schulz and Bora Ucar has been accepted at the European Symposium on Algorithms. You can find a preprint here. The second paper is "SubModST: A Fast Generic Solver for Submodular Maximization with Size Constraints" by Henning Martin Woydt, Christian Komusiewicz, Frank Sommer.

    20.6.2024: We are pleased to announce the publication of our new guide "Care for ME/CFS - Praxisleitfaden für die Versorgung von ME/CFS Betroffenen." authored by Astrid Hainzl, Johanna Rohrhofer, Johannes Schweighardt, Joachim Hermisson, Kathryn Hoffmann, Martin Komenda-Lett, Golda Schlaff, Christian Schulz, Michael Stingl, Kevin Thonhofer, and Eva Untersmayr. You can access the guide here.

    17.6.2024: Our paper "Finding Near-Optimum Weight Independent Sets at Scale" by Ernestine Großmann, Sebastian Lamm, Christian Schulz and Darren Strash, has been accepted at the Journal of Graph Algorithms and Applications.

    21.5.2024: We have new group member, Fabian Walliser who joined as a student research assistent -- Welcome!

    23.4.2024: We released a new technical report on computing optimal edge orientations. This is the main work of Henrik in collaboration with Bora Uçar. You can find the preprint here.

    23.4.2024: We released an update to our technical report on signed multilevel and memetic graph clustering. Our algorithm is now an order of magnitude faster than before. You can find a preprint here.

    16.4.2024: We have new scientific visitor, Kenneth Langedal -- Welcome!

    15.4.2024: We have new guest lecturer, Manuel Penschuck, who will read the Algorithms and Data Structures I course -- Welcome!

    27.3.2024: Two papers of the group have been accepted at the Symposium on Experimental Algorithms SEA24. The paper "Engineering Weighted Connectivity Augmentation Algorithms" by Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos, Thomas Möller, Christian Schulz and the paper "Buffered Streaming Edge Partitioning" by Adil Chhabra, Marcelo Fonseca Faraj, Daniel Seemaier, Christian Schulz.

    1.3.2024: We have new group member, Henning Woydt -- Welcome!

    1.11.2023: We have new group member, Adil Chhabra -- Welcome!

    19.10.2023: We released an open problems report on "Open Problems in (Hyper)Graph Decomposition". This has been joint work with organizers and participants of Dagstuhl Seminar 23331. You can find the report here.

    18.10.2023: Our DFG project proposal "Engineering Algorithms for Process Mapping at Scale" has been accepted.

    28.8.2023: Our group member Marcelo Fonseca Faraj successfully defended his PhD! Congratulations!

    18.7.2023: Our group receives the best paper award at the Symposium on Experimental Algorithms (SEA23) for the paper "FREIGHT: Fast Streaming Hypergraph Partitioning". Joint work of Kamal Eyubov, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.

    11.7.2023: A team of students in the algorithm engineering group aka Team HeiTwin (Dennis Jakob, Nikita-Nick Funk, Thomas Möller, Ernestine Großmann) has achieved remarkable success in the PACE Challenge! They secured the 5th place in the heuristic track (overall ranking) and an impressive 2nd place in the student ranking of the exact track of the challenge. Congratulations!

    23.6.2023: Our paper "Faster Local Motif Clustering via Maximum Flow" has been accepted at the European Symposium on Algorithms (ALGO/ESA). Joint work of Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.

    1.6.2023: We have new group member, Henrik Reinstädtler -- Welcome!

    26.4.2023: Prof. Stefan Neumann from KTH Stockholm gave a talk about his recent result "Dynamic Maintenance of Monotone Dynamic Programs and Applications". You can find the talk slides here. We are now actively searching for a master student to engeineer this type of dynamic dynamic programming algorithms in particular for the knapsack problem.

    31.3.2023: Our paper "Finding Near-Optimal Weight Independent Sets at Scale" has been accepted at the Genetic and Evolutionary Computation Conference (GECCO). Joint work of Ernestine Großmann, Sebastian Lamm, Christian Schulz and Darren Strash. You can find a preprint here.

    31.3.2023: Our paper "A Distributed Multilevel Memetic Algorithm for Signed Graph Clustering" has been accepted at the Genetic and Evolutionary Computation Conference (GECCO) as short-paper. Joint work of Felix Hausberger, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.

    27.3.2023: Our paper "FREIGHT: Fast Streaming Hypergraph Partitioning" has been accepted at the Symposium on Experimental Algorithms (SEA23). Joint work of Kamal Eyubov, Marcelo Fonseca Faraj and Christian Schulz. You can find a preprint here.

    27.3.2023: Our paper "Arc-Flags Meet Trip-Based Public Transit Routing" has been accepted at the Symposium on Experimental Algorithms (SEA23). Joint work of Ernestine Großmann, Jonas Sauer, Christian Schulz, Patrick Steil. You can find a preprint here.

    15.3.2023: Our DFG project proposal "Algorithm Engineering for Dynamic and (Re)Streaming Graph Decomposition Algorithms" has been accepted.

    8.3.2023: One paper of our group has been accepted at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23). The paper is titled "Engineering Fully Dynamic Delta Orientation Algorithms" and is joint work of Jannick Borowitz, Ernestine Großmann, Christian Schulz. You can find a preprint here.

    15.2.2023: Our group released a new report on "Arc-Flags Meet Trip-Based Public Transit Routing" joint work of Ernestine Großmann, Jonas Sauer, Christian Schulz, Patrick Steil. You can find it here.

    14.2.2023: Our group released a new report on "FREIGHT: Fast Streaming Hypergraph Partitioning" joint work of Kamal Eyubov, Marcelo Fonseca Faraj and Christian Schulz. You can find it here.

    2.2.2023: Our group released a new report on "Improved Exact and Heuristic Algorithms for Maximum Weight Clique" joint work of Roman Erhardt, Kathrin Hanauer, Nils Kriege, Christian Schulz, Darren Strash. You can find it here.

    19.1.2023: Our group released a new report on "Faster Local Motif Clustering via Maximum Flows" joint work of Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz. You can find it here.

    18.1.2023: Our group released a new report on "Engineering Fully Dynamic Delta Orientation Algorithms" joint work of Jannick Borowitz, Ernestine Großmann, Christian Schulz. You can find it here.

    26.10.2022: Our survey "More Recent Advances in Graph Partitioning" joint work of Ümit V. Çatalyürek, Karen D. Devine, Marcelo F. Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier and Dorothea Wagner, has been accepted at ACM Surveys. You can find a preprint here.

    15.10.2022: One paper of our group titled "Local Motif Clustering Via Hypergraph Partitioning" together with Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz has been accepted at ALENEX 2023. A preprint can be found here.

    28.9.2022: Prof. Dr. Christian Schulz joined the Steering Committee of the European Symposium on Algorithms (ALGO/ESA).

    30.8.2022: Prof. Dr. Christian Schulz is now part of the Steering Committee of Parameterized Algorithms and Computational Experiments (PACE).

    3.8.2022: Prof. Dr. Christian Schulz joined the Steering Committee of the Symposium on Experimental Algorithms.

    2.8.2022: Our survey "Recent Advances in Fully Dynamic Graph Algorithms" has been accepted for publication at the ACM Journal of Experimental Algorithms (JEA). You can find a preprint here.

    21.7.2022: Our paper "O'Reach: Even Faster Reachability in Large Graphs" by Kathrin Hanauer, Christian Schulz and Jonathan Trummer has been accepted for publication at at the special issue of the ACM Journal of Experimental Algorithms for SEA 2021. You can find a preprint here.

    11.7.2022: Proceedings of the Symposium on Experimental Algorithms SEA 2022 are out. SEA will happen in Heidelberg at the end of July! You can find it here.

    5.7.2022: Our paper "Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms for Hierarchical Graph Partitioning and Process Mapping" joint work of Marcelo Fonseca Faraj and Christian Schulz, has been accepted at IEEE Cluster. You can find a preprint here.

    28.6.2022: Our paper "Buffered Streaming Graph Partitioning" joint work of Marcelo Fonseca Faraj and Christian Schulz, has been accepted at Journal of Experimental Algorithms. You can find a preprint here.

    26.5.2022: We released a new survey "More Recent Advances in Graph Partitioning" joint work of Ümit V. Çatalyürek, Karen D. Devine, Marcelo F. Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier and Dorothea Wagner. You can find a preprint here.

    11.5.2022: We released a new technical report "Local Motif Clustering Via (Hyper)Graph Partitioning. joint work of Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz. This paper considers the local graph clustering problem with respect to motif conductance. You can find a preprint here.

    2.5.2022: Our manuscript entitled "Local Motif Clustering via (Hyper)Graph Partitioning" was accepted as extended abstract at AAAI International Symposium on Combinatorial Search.

    25.3.2022: Our manuscript entitled "High-Quality Hypergraph Partitioning" has been accepted for publication at ACM Journal of Experimental Algorithms. You can find a preprint here.

    14.3.2022: Our proposal for a Dagstuhl Meeting on "Recent Trends in Graph Partitioning" has been accepted. The meeting will take place in August 2023.

    4.3.2022: Our survey "Recent Advances in Fully Dynamic Graph Algorithms" will appear in the proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND).

    2.2.2022: We released a new technical report "Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms for Hierarchical Graph Partitioning and Process Mapping" joint work of Marcelo Fonseca Faraj and Christian Schulz. This paper considers the hierarchical streaming graph partitioning problem with applications to process mapping. You can find a preprint here.

    21.12.2021: Our minisymposium "Partitioning and Process Mapping for Emerging Architectures" has been accepted at SIAM Parallel Processing (SIAM PP). Joint work with Henning Meyerhenke and George Slota. This is a two part minisymposium. You can find the schedule here and here.

    06.12.2021: Prof. Dr. Christian Schulz joins the editorial board of ACM Transactions on Parallel Computing (TOPC) as an Associate Editor for the term January 2022 - December 2024.

    24.11.2021: The initial version of the website for SEA is online and available here

    22.11.2021: Prof. Dr. Christian Schulz will be the PC Chair of the Symposium on Experimental Algorithms 2022 (SEA'22). Moreover, SEA will take place in Heidelberg.

    17.11.2021: Our proposal "Machine Learning for Graph and Hypergraph Clustering Problems" which has been jointly submitted with Bora Ucar from Lyon has been accepted by DAAD. This will enable further cooperation between the Algorithm Engineering Group Heidelberg and Bora Ucar's group in Lyon, France.

    2.10.2021: One paper of the group "Practical Fully Dynamic Minimum Cut Algorithms" together with M. Henzinger and A. Noe has been accepted at ALENEX 2022. A preprint can be found here.

    20.9.2021: We currently have an open PhD or PostDoc position. See here for details!

    19.9.2021: Prof. Dr. Christian Schulz has been invited to give a talk at the Google Scalable Algorithms for Semi-supervised and Unsupervised Learning Workshop 2021.

    31.8.2021: Our paper "Faster Support Vector Machines" by Sebastian Schlag, Matthias Schmidt and Christian Schulz, has been accepted for publication at the ACM Journal of Experimental Algorithms (ACM JEA).

    3.8.2021: Our DFG project proposal "Algorithm Engineering for Scalable Data Reduction" has been accepted.

    24.6.2021: The paper "Deep Multilevel Graph Partitioning" by Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz and Daniel Seemaier has been accepted for publication at the 29th Annual European Symposium on Algorithms (ESA).

    17.6.2021: We released a new technical report "High Quality Hypergraph Partitioning" joint work with Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz and Peter Sanders. This paper considers the balanced hypergraph partitioning problem. In the TR, we describe all details of our open source hypergraph partitioner KaHyPar which is based on the successful multi-level approach. You can find a preprint here.

    9.6.2021: Prof. Dr. Christian Schulz will be PC Chair for the PACE'22 implementation challenge. Ernestine Grossmann, Tobias Heuer and Darren Strash are joining the program committee.

    6.5.2021: We released a new technical report on "Deep Multilevel Graph Partitioning" by Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, Daniel Seemaier. You can find a preprint here.

    6.5.2021: Two papers of the group have been accepted at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21). The paper "Fully-dynamic Weighted Matching Approximation in Practice" by Eugenio Angriman, Henning Meyerhenke, Christian Schulz, Bora Ucar and the paper "Faster Parallel Multiterminal Cuts" by Monika Henzinger, Alexander Noe, Christian Schulz.

    29.4.2021: The paper "An MPI-Parallel Algorithm for Mapping Complex Networks onto Hierarchical Architectures" by Maria Predarim, Charilaos Tzovas, Christian Schulz, Henning Meyerhenke has been accepted for publication at the 27th International European Conference on Parallel Computing (Euro-Par).

    28.4.2021: We released a new technical report on "Fully-dynamic Weighted Matching Approximation in Practice" joint work with Eugenio Angriman, Henning Meyerhenke, Christian Schulz and Bora Ucar. You can find a preprint here.

    9.3.2021: The paper "O'Reach: Even Faster Reachability in Large Graphs" by Kathrin Hanauer, Christian Schulz and Jonathan Trummer has been accepted for publication at the 19th Symposium on Experimental Algorithms (SEA). You can find a preprint here.

    1.3.2021: Our survey "Recent Advances in Scalable Graph Generation" together with Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders and Christian Schulz has been accepted as a book chapter for the Massive Graph Analytics book. You can find a preprint here.

    23.2.2021: We released a new survey on fully dynamic graph algorithms. You can find it here.

    19.2.2021: We released a new TR on buffered streaming graph partitioning. Faster and better than the previous state-of-the-art! You can find it here.

    1.2.2021: We have new group member, Ernestine Grossmann -- Welcome!

    23.12.2020: We released a survey on recent advances in practical data reduction. It is available here.

    16.11.2020: We released mt-KaHIP -- shared-memory parallel high quality graph partitioning. It can be found here.

    10.11.2020: One paper of the group "The Future is Big Graphs! A Community View on Graph Processing Systems" together with Sakr et. al has been accepted at Communications of ACM (CACM). A preprint can be found here.

    5.10.2020: Four papers of the group have been accepted at SIAM Symposium on Algorithm Engineering and Experiments (ALENEX21).

    1.10.2020: Covid-19: Due to the ongoing Coronavirus situation, lectures and seminars in the upcomping winter semester 2020/21 will be done online.

    1.10.2020: We started! On October 1st, our group arrived in the new offices in Heidelberg. In somnis veritas.