3 papers
cs.DC2025
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…
cs.DS2025
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…
math.OC2024
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…