6 citations · 27 across the 32 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.SI2016★ 5 cited
Greedy Routing and the Algorithmic Small-World Phenomenom
Karl Bringmann, Ralph Keusch, Johannes Lengler +2
The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However,…
cs.DS2016★ 1 cited
On the Complexity of Local Distributed Graph Problems
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus
This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for ma…
cs.DC2016★ 4 cited
Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
Dan Hefetz, Fabian Kuhn, Yannic Maus +1
We show an lower bound on the runtime of any deterministic distributed -graph coloring algorithm in a weak vari…