15 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…
Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
Ernestine Großmann, Christian Schulz, Darren Strash +1
This work addresses the well-known Maximum Independent Set problem in the context of hypergraphs. While this problem has been extensively studied on graphs, we focus on its strong…
Efficient Parallel Algorithms for Hypergraph Matching
Henrik Reinstädtler, Christian Schulz, Nodari Sitchinava +1
We present efficient parallel algorithms for computing maximal matchings in hypergraphs. Our algorithm finds locally maximal edges in the hypergraph and adds them in parallel to th…
Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
Jannick Borowitz, Ernestine Großmann, Christian Schulz
A 2-packing set for an undirected, weighted graph G=(V,E,w) is a subset S of the vertices V such that any two vertices are not adjacent and have no common neighbors. The Maximum We…
Semi-Streaming Algorithms for Hypergraph Matching
Henrik Reinstädtler, S M Ferdous, Alex Pothen +2
We propose two one-pass streaming algorithms for the -hard hypergraph matching problem. The first algorithm stores a small subset of potential matching edges in a sta…
Accelerating Reductions Using Graph Neural Networks and a New Concurrent Local Search for the Maximum Weight Independent Set Problem
Ernestine Großmann, Kenneth Langedal, Christian Schulz
The Maximum Weight Independent Set problem is a fundamental NP-hard problem in combinatorial optimization with several real-world applications. Given an undirected vertex-weighted…
A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
Ernestine Großmann, Kenneth Langedal, Christian Schulz
The Maximum Weight Independent Set (MWIS) problem, as well as its related problems such as Minimum Weight Vertex Cover, are fundamental NP-hard problems with numerous practical app…
Engineering Hypergraph -Matching Algorithms
Ernestine Großmann, Felix Joos, Henrik Reinstädtler +1
Recently, researchers have extended the concept of matchings to the more general problem of finding -matchings in hypergraphs broadening the scope of potential applications and…
Engineering Fully Dynamic Exact -Orientation Algorithms
Ernestine Großmann, Henrik Reinstädtler, Christian Schulz +1
A (fully) dynamic graph algorithm is a data structure that supports edge insertions, edge deletions, and answers specific queries pertinent to the problem at hand. In this work, we…
Optimal Neighborhood Exploration for Dynamic Independent Sets
Jannick Borowitz, Ernestine Großmann, Christian Schulz
A dynamic graph algorithm is a data structure that supports edge insertions, deletions, and specific problem queries. While extensive research exists on dynamic algorithms for grap…
Engineering Edge Orientation Algorithms
H. Reinstädtler, C. Schulz, B. Uçar
Given an undirected graph G, the edge orientation problem asks for assigning a direction to each edge to convert G into a directed graph. The aim is to minimize the maximum out deg…
Buffered Streaming Edge Partitioning
Adil Chhabra, Marcelo Fonseca Faraj, Christian Schulz +1
Addressing the challenges of processing massive graphs, which are prevalent in diverse fields such as social, biological, and technical networks, we introduce HeiStreamE and Freigh…
Engineering Weighted Connectivity Augmentation Algorithms
Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos +2
Increasing the connectivity of a graph is a pivotal challenge in robust network design. The weighted connectivity augmentation problem is a common version of the problem that takes…
FLASH-TB: Integrating Arc-Flags and Trip-Based Public Transit Routing
Ernestine Großmann, Jonas Sauer, Christian Schulz +2
We present FLASH-TB, a journey planning algorithm for public transit networks that combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. The basic i…
Open Problems in (Hyper)Graph Decomposition
Deepak Ajwani, Rob H. Bisseling, Katrin Casel +26
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gai…