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

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa

Date

2021-10-01

Major/Subject

Mcode

Degree programme

Language

en

Pages

4

Series

35th International Symposium on Distributed Computing, DISC 2021, Leibniz International Proceedings in Informatics, LIPIcs, Volume 209

Abstract

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).

Description

| openaire: EC/H2020/805223/EU//ScaleML

Keywords

Round elimination, Sinkless orientation, Supported LOCAL model

Other note

Citation

Korhonen, J H, Paz, A, Rybicki, J, Schmid, S & Suomela, J 2021, Brief announcement: Sinkless orientation is hard also in the supported LOCAL model . in S Gilbert (ed.), 35th International Symposium on Distributed Computing, DISC 2021 ., 58, Leibniz International Proceedings in Informatics, LIPIcs, vol. 209, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Freiburg, Germany, 04/10/2021 . https://doi.org/10.4230/LIPIcs.DISC.2021.58