26 citations · 100 across the 29 of their papers we have counts for
6 papers · 1 filter
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus +1
We present a deterministic distributed algorithm, in the LOCAL model, that computes a -edge-coloring in polylogarithmic-time, so long as the maximum degree $Δ=\tildeΩ(\l…
Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma
Yi-Jun Chang, Qizheng He, Wenzheng Li +2
We explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. Lower Bounds: First, we simplify the round elimination technique of Brandt et al…
Dynamic Networks of Finite State Machines
Yuval Emek, Jara Uitto
Like distributed systems, biological multicellular processes are subject to dynamic changes and a biological system will not pass the survival-of-the-fittest test unless it exhibit…
Improved Distributed Degree Splitting and Edge Coloring
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn +3
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discre…
Tight Bounds for Asynchronous Collaborative Grid Exploration
Sebastian Brandt, Jara Uitto, Roger Wattenhofer
Consider a small group of mobile agents whose goal is to locate a certain cell in a two-dimensional infinite grid. The agents operate in an asynchronous environment, where in each…
Exploring an Infinite Space with Finite Memory Scouts
Lihi Cohen, Yuval Emek, Oren Louidor +1
Consider a small number of scouts exploring the infinite -dimensional grid with the aim of hitting a hidden target point. Each scout is controlled by a probabilistic finite auto…