686 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Fachhochschule SalzburgAT17 papers
- Graz University of TechnologyAT16 papers
- University of ViennaAT15 papers
- Johannes Kepler University of LinzAT13 papers
- TU WienAT12 papers
- Pädagogische Hochschule SalzburgAT10 papers
- University of Electro-CommunicationsJP10 papers
- Paul Scherrer InstituteCH9 papers
- Vienna University of Economics and BusinessAT9 papers
- Centre National de la Recherche ScientifiqueFR8 papers
- Institut Laue-LangevinFR8 papers
- Austrian Academy of SciencesAT7 papers
8 papers · 1 filter
Fast Algorithms for Energy Games in Special Cases
Sebastian Forster, Antonis Skarlatos, Tijn de Vos
In this paper, we study algorithms for special cases of energy games, a class of turn-based games on graphs that show up in the quantitative analysis of reactive systems. In an ene…
Minor Sparsifiers and the Distributed Laplacian Paradigm
Sebastian Forster, Gramoz Goranci, Yang P. Liu +3
We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrice…
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Aaron Bernstein, Sebastian Forster, Monika Henzinger
Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, wher…
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster, Gramoz Goranci
Spanning trees of low average stretch on the non-tree edges, as introduced by Alon et al. [SICOMP 1995], are a natural graph-theoretic object. In recent years, they have found sign…
A Note on Hardness of Diameter Approximation
Karl Bringmann, Sebastian Krinninger
We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, rounds are necessary to compute the diameter [Fri…
Breaking the log n barrier on rumor spreading
Chen Avin, Robert Elsässer
rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching low…
On the Influence of Graph Density on Randomized Gossiping
Robert Elsässer, Dominik Kaaser
Information dissemination is a fundamental problem in parallel and distributed computing. In its simplest variant, the broadcasting problem, a message has to be spread among all no…
The Power of Two Choices in Distributed Voting
Colin Cooper, Robert Elsässer, Tomasz Radzik
Distributed voting is a fundamental topic in distributed computing. In pull voting, in each step every vertex chooses a neighbour uniformly at random, and adopts its opinion. The v…