2 citations · 2 across the 14 of their papers we have counts for
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…
Distributed Reductions for the Maximum Weight Independent Set Problem
Jannick Borowitz, Ernestine Großmann, Mattthias Schimek
Finding maximum-weight independent sets in graphs is an important NP-hard optimization problem. Given a vertex-weighted graph , the task is to find a subset of pairwise non-adja…
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…
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 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…
Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
Jannick Borowitz, Ernestine Großmann, Christian Schulz +1
A 2-packing set for an undirected graph is a subset such that any two vertices have no common neighbors. Finding a 2-pac…
Arc-Flags Meet Trip-Based Public Transit Routing
Ernestine Großmann, Jonas Sauer, Christian Schulz +1
We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compare…
Engineering Fully Dynamic -Orientation Algorithms
Jannick Borowitz, Ernestine Großmann, Christian Schulz
A (fully) dynamic graph algorithm is a data structure that supports edge insertions, edge deletions, and answers certain queries that are specific to the problem under consideratio…
Finding Near-Optimal Weight Independent Sets at Scale
Ernestine Großmann, Sebastian Lamm, Christian Schulz +1
Computing maximum weight independent sets in graphs is an important NP-hard optimization problem. The problem is particularly difficult to solve in large graphs for which data redu…