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