5 papers
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…
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…
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…
Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
Jannick Borowitz, Ernestine Großmann, Christian Schulz +1
A 2-packing set for an undirected graph is a subset such that any two vertices have no common neighbors. Finding a 2-pac…
Engineering Fully Dynamic -Orientation Algorithms
Jannick Borowitz, Ernestine Großmann, Christian Schulz
A (fully) dynamic graph algorithm is a data structure that supports edge insertions, edge deletions, and answers certain queries that are specific to the problem under consideratio…