8 papers · 1 filter
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 Edge Orientation Algorithms
H. Reinstädtler, C. Schulz, B. Uçar
Given an undirected graph G, the edge orientation problem asks for assigning a direction to each edge to convert G into a directed graph. The aim is to minimize the maximum out deg…
Buffered Streaming Edge Partitioning
Adil Chhabra, Marcelo Fonseca Faraj, Christian Schulz +1
Addressing the challenges of processing massive graphs, which are prevalent in diverse fields such as social, biological, and technical networks, we introduce HeiStreamE and Freigh…
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…