37 citations · 142 across the 37 of their papers we have counts for
5 papers · 1 filter
On the Impact of Identifiers on Local Decision
Pierre Fraigniaud, Magnús Halldórsson, Amos Korman
The issue of identifiers is crucial in distributed computing. Informally, identities are used for tackling two of the fundamental difficulties that areinherent to deterministic dis…
Max Point-Tolerance Graphs
Daniele Catanzaro, Steven Chaplick, Stefan Felsner +4
A graph is a \emph{max point-tolerance (MPT)} graph if each vertex of can be mapped to a \emph{pointed-interval} where is an interval of …
A Local Broadcast Layer for the SINR Network Model
Magnus M. Halldorsson, Stephan Holzer, Nancy Lynch
We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that effi…
The Price of Local Power Control in Wireless Scheduling
Magnus M. Halldorsson, Tigran Tonoyan
We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum n…
Semi-Transitive Orientations and Word-Representable Graphs
Magnús M. Halldórsson, Sergey Kitaev, Artem Pyatkin
A graph is a \emph{word-representable graph} if there exists a word over the alphabet such that letters and alternate in if and only if f…