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

    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.