Janne H. Korhonen · Ami Paz · Joel Rybicki · Stefan Schmid · Jukka Suomela

Brief announcement: Sinkless orientation is hard also in the supported LOCAL model

DISC 2021 · 35th International Symposium on Distributed Computing, online, October 2021

authors’ version arXiv.org

Abstract

We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires $\Omega(\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 $\Omega(\log n)$.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.