7 papers
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…
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…
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…
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…
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…