9 citations · 15 across the 5 of their papers we have counts for
6 papers
Constant Approximation of Arboricity in Near-Optimal Sublinear Time
Jiangqi Dai, Mohsen Ghaffari, Julian Portmann
We present a randomized algorithm that computes a constant approximation of a graph's arboricity, using queries to adjacency lists and in the same time bound. Here…
Distributed MIS with Low Energy and Time Complexities
Mohsen Ghaffari, Julian Portmann
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy…
Average Awake Complexity of MIS and Matching
Mohsen Ghaffari, Julian Portmann
Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the notion of awake complexity for distributed algorithms, which measures the number of rounds in which a node is…
Tight Bounds for Deterministic High-Dimensional Grid Exploration
Sebastian Brandt, Julian Portmann, Jara Uitto
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are require…
k-means++: few more steps yield constant approximation
Davin Choo, Christoph Grunau, Julian Portmann +1
The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approxim…
Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond
Mohsen Ghaffari, Julian Portmann
Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and Plotkin [FOCS'89], are one of the key algorithmic tools in distributed graph algorithms. We present an improv…