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

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

2 Lataukset (Pure)

Abstrakti

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

AlkuperäiskieliEnglanti
Otsikko35th International Symposium on Distributed Computing, DISC 2021
ToimittajatSeth Gilbert
KustantajaSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Sivumäärä4
ISBN (elektroninen)9783959772105
DOI - pysyväislinkit
TilaJulkaistu - 1 lokakuuta 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Distributed Computing - Virtual, Online, Freiburg, Saksa
Kesto: 4 lokakuuta 20218 lokakuuta 2021
Konferenssinumero: 35

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Vuosikerta209
ISSN (painettu)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC
Maa/AlueSaksa
KaupunkiFreiburg
Ajanjakso04/10/202108/10/2021

Siteeraa tätä