The paper “Cooperation in Bilateral Generalized Network Creation” was written by Lukas Weyand, Hans Gawendowicz and Pascal Lenzner will be presented at the WINE conference on December 8 - 11 at Rutgers University, New Brunswick, USA. While the original network creation game has a price of anarchy (PoA) that is constant for almost the whole range of the price parameter α, the generalized version of the model with arbitrary edge weights has a high PoA in Θ (α). We introduce a new model, the bilateral generalized network creation game, which additionally incorporates cooperation between agents. We show that with both metric edge weights and a high amount of cooperation, the PoA can be improved to O(sqrt{α}) for most ranges of α.
The paper "On Distributed Colouring of Hyperbolic Random Graphs" was written by Janosch Ruff with Yannic Maus for the ACM-SIAM Symposium on Discrete Algorithms (SODA26) which takes place on 11-14 January in Vancouver, Canada. Distributed Colouring is an algorithmic problem which was studied intenstively in the last few decades and very involved techniques were developed over this time. The authors use hyperbolic random graphs which is a widely accepted model for many real-world networks like the internet or social networks and show that a very simple (randomised) algorithm colours such networks much faster and with less colours than any of these suffisticated approaches would use.
"Temporal Exploration of Random Spanning Tree Models" was written by Nicolas Klodt, George Skretas, Andreas Göbel and Samuel Baguley and will be presented at the SODA Conference from 11th to 14th of January 2026 in Vancouver, Canada. Temporal graphs are used to model networks with edges that are not always present, like train networks. A well studied problem on those graphs is how long an explorer takes to visit all vertices in the graph in the worst case. This paper analyzes the average case by studying the same problem on random temporal graphs that are obtained by choosing each snapshot independently from some distribution over spanning trees.
