Opin vísindi

Browsing by Journal title "Theoretical Computer Science"

Browsing by Journal title "Theoretical Computer Science"

Sort by: Order: Results:

  • Halldórsson, Magnús M.; Konrad, Christian (Elsevier BV, 2020-04)
    We give a distributed (1+eps)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O((1/eps) log* n) rounds. If nodes are aware of their interval representations, then the ...
  • Halldórsson, Magnús M.; Holzer, Stephan; Markatou, Evangelia Anna; Lynch, Nancy (Elsevier BV, 2020-04)
    We consider the Leader Election Problem in the Signal-to-Interference-plusNoise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to elect a leader in two communication rounds, with high ...