13 citations · 39 across the 12 of their papers we have counts for
18 papers
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 Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place
Manuel Penschuck
Shuffling is the process of rearranging a sequence of elements into a random order such that any permutation occurs with equal probability. It is an important building block in a p…
Parallel and I/O-Efficient Algorithms for Non-Linear Preferential Attachment
Daniel Allendorf, Ulrich Meyer, Manuel Penschuck +1
Preferential attachment lies at the heart of many network models aiming to replicate features of real world networks. To simulate the attachment process, conduct statistical tests,…
Algorithms for Large-scale Network Analysis and the NetworKit Toolkit
Eugenio Angriman, Alexander van der Grinten, Michael Hamann +2
The abundance of massive network data in a plethora of applications makes scalable analysis algorithms and software tools necessary to generate knowledge from such data in reasonab…
Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees
Daniel Allendorf, Ulrich Meyer, Manuel Penschuck +1
The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g. to construct graph generators or null-models. Here, the Ed…
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…
Efficient and accurate group testing via Belief Propagation: an empirical study
AminCoja-Oghlan, Max Hahn-Klimroth, Philipp Loick +1
The group testing problem asks for efficient pooling schemes and algorithms that allow to screen moderately large numbers of samples for rare infections. The goal is to accurately…
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…
Near optimal sparsity-constrained group testing: improved bounds and algorithms
Oliver Gebhard, Max Hahn-Klimroth, Olaf Parczyk +4
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the subli…
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…
The random 2-SAT partition function
Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth +4
We show that throughout the satisfiable phase the normalised number of satisfying assignments of a random -SAT formula converges in probability to an expression predicted by the…
Bidirectional Text Compression in External Memory
Patrick Dinklage, Jonas Ellert, Johannes Fischer +2
Bidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such a…
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann +3
Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks…
Fragile Complexity of Comparison-Based Algorithms
Peyman Afshani, Rolf Fagerberg, David Hammer +5
We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the ma…
Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades
Corrie Jacobien Carstens, Michael Hamann, Ulrich Meyer +3
Graph randomisation is a crucial task in the analysis and synthesis of networks. It is typically implemented as an edge switching process (ESMC) repeatedly swapping the nodes of ra…
I/O-Efficient Generation of Massive Graphs Following the LFR Benchmark
Michael Hamann, Ulrich Meyer, Manuel Penschuck +2
LFR is a popular benchmark graph generator used to evaluate community detection algorithms. We present EM-LFR, the first external memory algorithm able to generate massive complex…