9 papers · 1 filter
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…
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…
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…