Brief Announcement: Sinkless Orientation is Hard also in the Supported LOCAL Model

AutorKorhonen, Janne H.; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Suomela, Jukka
ArtConference Paper
AbstraktWe show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).
KonferenzInternational Symposium on Distributed Computing (DISC) <35, 2021, Freiburg; Online>
ReferenzGilbert, S.: 35th International Symposium on Distributed Computing, DISC 2021: October 4-8, 2021, Freiburg, Germany, (virtual conference). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. (Leibniz International Proceedings in Informatics. LIPIcs 209), pp. 58:1-58:4
SchlüsselISBN : 9783959772105