5 papers · 1 filter
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…
Certifying Induced Subgraphs in Large Graphs
Ulrich Meyer, Hung Tran, Konstantinos Tsakalidis
We introduce I/O-optimal certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input g…
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…
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…