License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.58
URN: urn:nbn:de:0030-drops-148609
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14860/
Korhonen, Janne H. ;
Paz, Ami ;
Rybicki, Joel ;
Schmid, Stefan ;
Suomela, Jukka
Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model
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).
BibTeX - Entry
@InProceedings{korhonen_et_al:LIPIcs.DISC.2021.58,
author = {Korhonen, Janne H. and Paz, Ami and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka},
title = {{Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {58:1--58:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14860},
URN = {urn:nbn:de:0030-drops-148609},
doi = {10.4230/LIPIcs.DISC.2021.58},
annote = {Keywords: Supported LOCAL model, sinkless orientation, round elimination}
}
|
Keywords: |
|
Supported LOCAL model, sinkless orientation, round elimination |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
