26 citations · 35 across the 8 of their papers we have counts for
14 papers
Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts
David A. Bader, Adil Chhabra, Ernestine Großmann +3
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last y…
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: Given a node-weighted graph, find a set of independent (mutually nona…
Algorithm Engineering for Cut Problems
Alexander Noe
Graphs are a natural representation of data from various contexts, such as social connections, the web, road networks, and many more. In the last decades, many of these networks ha…
Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm Performs Best in Practice?
Monika Henzinger, Alexander Noe
Fully dynamic graph algorithms that achieve polylogarithmic or better time per operation use either a hierarchical graph decomposition or random-rank based approach. There are so f…
New instances for maximum weight independent set from a vehicle routing application
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve…
Practical Fully Dynamic Minimum Cut Algorithms
Monika Henzinger, Alexander Noe, Christian Schulz
We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical…
Recent Advances in Practical Data Reduction
Faisal Abu-Khzam, Sebastian Lamm, Matthias Mnich +3
Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has res…
Faster Parallel Multiterminal Cuts
Monika Henzinger, Alexander Noe, Christian Schulz
We give an improved branch-and-bound solver for the multiterminal cut problem, based on the recent work of Henzinger et al.. We contribute new, highly effective data reduction rule…
Finding All Global Minimum Cuts In Practice
Monika Henzinger, Alexander Noe, Christian Schulz +1
We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph…
Shared-Memory Branch-and-Reduce for Multiterminal Cuts
Monika Henzinger, Alexander Noe, Christian Schulz
We introduce the fastest known exact algorithm~for~the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use t…
Shared-memory Exact Minimum Cuts
Monika Henzinger, Alexander Noe, Christian Schulz
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. In this paper, we…
ILP-based Local Search for Graph Partitioning
Alexandra Henzinger, Alexander Noe, Christian Schulz
Computing high-quality graph partitions is a challenging problem with numerous applications. In this paper, we present a novel meta-heuristic for the balanced graph partitioning pr…
Practical Minimum Cut Algorithms
Monika Henzinger, Alexander Noe, Christian Schulz +1
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduc…
Algorithms for Mapping Parallel Processes onto Grid and Torus Architectures
Roland Glantz, Henning Meyerhenke, Alexander Noe
Static mapping is the assignment of parallel processes to the processing elements (PEs) of a parallel system, where the assignment does not change during the application's lifetime…