Sinkless Orientation Made Simple

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorBalliu, Alkidaen_US
dc.contributor.authorKorhonen, Janne H.en_US
dc.contributor.authorKühn, Fabianen_US
dc.contributor.authorLievonen, Henriken_US
dc.contributor.authorOlivetti, Dennisen_US
dc.contributor.authorPai, Shreyasen_US
dc.contributor.authorPaz, Amien_US
dc.contributor.authorRybicki, Joelen_US
dc.contributor.authorSchmid, Stefanen_US
dc.contributor.authorStudený, Janen_US
dc.contributor.authorSuomela, Jukkaen_US
dc.contributor.authorUitto, Jaraen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorProfessorship Suomela J.en
dc.contributor.groupauthorComputer Science Professorsen
dc.contributor.groupauthorComputer Science - Large-scale Computing and Data Analysis (LSCA)en
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS)en
dc.contributor.groupauthorProfessorship Uitto J.en
dc.contributor.organizationUniversity of Freiburgen_US
dc.contributor.organizationUniversity of Viennaen_US
dc.contributor.organizationIST Austriaen_US
dc.contributor.organizationAalborg Universityen_US
dc.contributor.organizationGran Sasso Science Instituteen_US
dc.date.accessioned2023-11-01T10:13:23Z
dc.date.available2023-11-01T10:13:23Z
dc.date.issued2023-01-12en_US
dc.description.abstractThe sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is Ω(log n) in the deterministic LOCAL model and O(log log n) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.en
dc.description.versionPeer revieweden
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationBalliu, A, Korhonen, J H, Kühn, F, Lievonen, H, Olivetti, D, Pai, S, Paz, A, Rybicki, J, Schmid, S, Studený, J, Suomela, J & Uitto, J 2023, Sinkless Orientation Made Simple . in 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023 . Society for Industrial and Applied Mathematics, Symposium on Simplicity in Algorithms, Florence, Italy, 23/01/2023 . https://doi.org/10.1137/1.9781611977585.ch17en
dc.identifier.doi10.1137/1.9781611977585.ch17en_US
dc.identifier.isbn978-1-61197-758-5
dc.identifier.otherPURE UUID: 432153e1-fe0f-4665-8dae-69a1bebbf3bden_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/432153e1-fe0f-4665-8dae-69a1bebbf3bden_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/126567730/Sinkless_Orientation_Made_Simple.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/124358
dc.identifier.urnURN:NBN:fi:aalto-202311016726
dc.language.isoenen
dc.relation.ispartofSymposium on Simplicity in Algorithmsen
dc.relation.ispartofseries2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023en
dc.rightsopenAccessen
dc.titleSinkless Orientation Made Simpleen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionpublishedVersion

Files

Collections

[article-cris] Perustieteiden korkeakoulu / SCI