7 citations · 10 across the 3 of their papers we have counts for
10 papers · 1 filter
Revisiting a Successful Reduction Rule for Dominating Set
Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3
Given a graph with vertices and edges, the DominatingSet problem asks for a set of minimal cardinality such that every vertex either is in …
Efficient Uniform Negative Edge Weights
Lukas Geis, Daniel Allendorf, Thomas Bläsius +4
We consider a maximum entropy edge weight model that allows for negative weights. Given a graph and possible weights typically consisting of positive and negative…
Insights into -shortcutting algorithms
Alexander Leonhardt, Ulrich Meyer, Manuel Penschuck
A graph is called a -graph iff every node can reach of its nearest neighbors in at most k hops. This property proved useful in the analysis and design of parallel shorte…
Engineering Uniform Sampling of Graphs with a Prescribed Power-law Degree Sequence
Daniel Allendorf, Ulrich Meyer, Manuel Penschuck +2
We consider the following common network analysis problem: given a degree sequence return a uniform sample from the ensemble of all…
Simulating Population Protocols in Sub-Constant Time per Interaction
Petra Berenbrink, David Hammer, Dominik Kaaser +3
We consider the problem of efficiently simulating population protocols. In the population model, we are given a distributed system of agents modeled as identical finite-state m…
Recent Advances in Scalable Network Generation
Manuel Penschuck, Ulrik Brandes, Michael Hamann +5
Random graph models are frequently used as a controllable and versatile data source for experimental campaigns in various research fields. Generating such data-sets at scale is a n…