• English
  • Deutsch
  • Log In
    Password Login
    Research Outputs
    Fundings & Projects
    Researchers
    Institutes
    Statistics
Repository logo
Fraunhofer-Gesellschaft
  1. Home
  2. Fraunhofer-Gesellschaft
  3. Konferenzschrift
  4. Brief Announcement: Sinkless Orientation is Hard also in the Supported LOCAL Model
 
  • Details
  • Full
Options
2021
Conference Paper
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 O(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 O(log n).
Author(s)
Korhonen, Janne H.
Paz, Ami
Rybicki, Joel
Schmid, Stefan  
Suomela, Jukka
Mainwork
35th International Symposium on Distributed Computing, DISC 2021  
Conference
International Symposium on Distributed Computing (DISC) 2021  
DOI
10.4230/LIPIcs.DISC.2021.58
Language
English
Fraunhofer-Institut für Sichere Informationstechnologie SIT  
  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Contact
© 2024