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

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

doi:10.4230/LIPIcs.DISC.2021.58

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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

1 Citation (Scopus)

21 Downloads (Pure)

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

Original language	English
Title of host publication	35th International Symposium on Distributed Computing, DISC 2021
Editors	Seth Gilbert
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	4
ISBN (Electronic)	9783959772105
DOIs	https://doi.org/10.4230/LIPIcs.DISC.2021.58
Publication status	Published - 1 Oct 2021
MoE publication type	A4 Conference publication
Event	International Symposium on Distributed Computing - Virtual, Online, Freiburg, Germany Duration: 4 Oct 2021 → 8 Oct 2021 Conference number: 35

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume	209
ISSN (Print)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Abbreviated title	DISC
Country/Territory	Germany
City	Freiburg
Period	04/10/2021 → 08/10/2021

Keywords

Round elimination
Sinkless orientation
Supported LOCAL model

Access to Document

10.4230/LIPIcs.DISC.2021.58

Brief announcement_Sinkless orientation is hard also in the supported LOCAL modelFinal published version, 438 KBLicence: CC BY

Cite this

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 Article 58 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 209). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.58

@inproceedings{b2f12b6ac43c4b6883a017df5d6bdae2,

title = "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).",

keywords = "Round elimination, Sinkless orientation, Supported LOCAL model",

author = "Korhonen, {Janne H.} and Ami Paz and Joel Rybicki and Stefan Schmid and Jukka Suomela",

note = "| openaire: EC/H2020/805223/EU//ScaleML ; International Symposium on Distributed Computing, DISC ; Conference date: 04-10-2021 Through 08-10-2021",

year = "2021",

month = oct,

day = "1",

doi = "10.4230/LIPIcs.DISC.2021.58",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Seth Gilbert",

booktitle = "35th International Symposium on Distributed Computing, DISC 2021",

address = "Germany",

}

Korhonen, JH, 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

Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. / Korhonen, Janne H.; Paz, Ami; Rybicki, Joel et al.
35th International Symposium on Distributed Computing, DISC 2021. ed. / Seth Gilbert. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. 58 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 209).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

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

AU - Korhonen, Janne H.

AU - Paz, Ami

AU - Rybicki, Joel

AU - Schmid, Stefan

AU - Suomela, Jukka

N1 - Conference code: 35

PY - 2021/10/1

Y1 - 2021/10/1

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

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

KW - Round elimination

KW - Sinkless orientation

KW - Supported LOCAL model

UR - http://www.scopus.com/inward/record.url?scp=85118114973&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.DISC.2021.58

DO - 10.4230/LIPIcs.DISC.2021.58

M3 - Conference article in proceedings

AN - SCOPUS:85118114973

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 35th International Symposium on Distributed Computing, DISC 2021

A2 - Gilbert, Seth

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Symposium on Distributed Computing

Y2 - 4 October 2021 through 8 October 2021

ER -

Korhonen JH, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In Gilbert S, editor, 35th International Symposium on Distributed Computing, DISC 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2021. 58. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.DISC.2021.58

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this