14 citations · 25 across the 8 of their papers we have counts for
11 papers · 1 filter
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 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…
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…