2026-07-23T08:48:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14860 2024-03-06T10:55:02Z ddc:004 open_access

Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model Korhonen, Janne H. Paz, Ami Rybicki, Joel Schmid, Stefan Suomela, Jukka Supported LOCAL model sinkless orientation round elimination We 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Janne H. Korhonen and Ami Paz and Joel Rybicki and Stefan Schmid and Jukka Suomela 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.58 urn:nbn:de:0030-drops-148609 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.58 eng https://creativecommons.org/licenses/by/4.0/legalcode