14 citations · 25 across the 8 of their papers we have counts for
15 papers
Deterministic Parallel High-Quality Hypergraph Partitioning
Robert Krause, Lars Gottesbüren, Nikolai Maas
We present a deterministic parallel multilevel algorithm for balanced hypergraph partitioning that matches the state of the art for non-deterministic algorithms. Deterministic para…
Linear-Time Multilevel Graph Partitioning via Edge Sparsification
Lars Gottesbüren, Nikolai Maas, Dominik Rosch +2
The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as singl…
Tera-Scale Multilevel Graph Partitioning
Daniel Salwasser, Daniel Seemaier, Lars Gottesbüren +1
We present TeraPart, a memory-efficient multilevel graph partitioning method that is designed to scale to extremely large graphs. In balanced graph partitioning, the goal is to div…
Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search
Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram +1
We consider the fundamental problem of decomposing a large-scale approximate nearest neighbor search (ANNS) problem into smaller sub-problems. The goal is to partition the input po…
Parallel Unconstrained Local Search for Partitioning Irregular Graphs
Nikolai Maas, Lars Gottesbüren, Daniel Seemaier
We present new refinement heuristics for the balanced graph partitioning problem that break with an age-old rule. Traditionally, local search only permits moves that keep the block…
Scalable High-Quality Hypergraph Partitioning
Lars Gottesbüren, Tobias Heuer, Nikolai Maas +2
Balanced hypergraph partitioning is an NP-hard problem with many applications, e.g., optimizing communication in distributed data placement problems. The goal is to place all nodes…
Parallel Flow-Based Hypergraph Partitioning
Lars Gottesbüren, Tobias Heuer, Peter Sanders
We present a shared-memory parallelization of flow-based refinement, which is considered the most powerful iterative improvement technique for hypergraph partitioning at the moment…
Deterministic Parallel Hypergraph Partitioning
Lars Gottesbüren, Michael Hamann
Balanced hypergraph partitioning is a classical NP-hard optimization problem with applications in various domains such as VLSI design, simulating quantum circuits, optimizing data…
Deep Multilevel Graph Partitioning
Lars Gottesbüren, Tobias Heuer, Peter Sanders +2
Partitioning a graph into blocks of "roughly equal" weight while cutting only few edges is a fundamental problem in computer science with a wide range of applications. In particula…
Shared-Memory n-level Hypergraph Partitioning
Lars Gottesbüren, Tobias Heuer, Peter Sanders +1
We present a shared-memory algorithm to compute high-quality solutions to the balanced -way hypergraph partitioning problem. This problem asks for a partition of the vertex set…
Scalable Shared-Memory Hypergraph Partitioning
Lars Gottesbüren, Tobias Heuer, Peter Sanders +1
Hypergraph partitioning is an important preprocessing step for optimizing data placement and minimizing communication volumes in high-performance computing applications. To cope wi…
Engineering Exact Quasi-Threshold Editing
Lars Gottesbüren, Michael Hamann, Philipp Schoch +3
Quasi-threshold graphs are -free graphs, i.e., they do not contain any cycle or path of four nodes as an induced subgraph. We study the -free editing pr…
Advanced Flow-Based Multilevel Hypergraph Partitioning
Lars Gottesbüren, Michael Hamann, Sebastian Schlag +1
The balanced hypergraph partitioning problem is to partition a hypergraph into disjoint blocks of bounded size such that the sum of the number of blocks connected by each hyper…
Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
Lars Gottesbüren, Michael Hamann, Dorothea Wagner
In this paper, we propose HyperFlowCutter, an algorithm for balanced hypergraph bipartitioning. It is based on minimum S-T hyperedge cuts and maximum flows. It computes a sequence…
Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
Lars Gottesbüren, Michael Hamann, Tim Niklas Uhl +1
Graph partitioning has many applications. We consider the acceleration of shortest path queries in road networks using Customizable Contraction Hierarchies (CCH). It is based on co…