Publications
Sinkless Orientation Made Simple
| Author | Balliu, Alkida; Korhonen, Janne H.; Kuhn, Fabian; Lievonen, Henrik; Olivetti, Dennis; Pai, Shreyas; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Studený, Jan; Suomela, Jukka; Uitto, Jara |
|---|---|
| Date | 2023 |
| Type | Conference Paper |
| Abstract | The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them. |
| Conference | Symposium on Simplicity in Algorithms 2023 |
| Url | https://publica.fraunhofer.de/handle/publica/462611 |
