153 citations
- Sobolev Institute of MathematicsRU3 papers
- Centrum Wiskunde & InformaticaNL2 papers
- University of StrathclydeGB2 papers
- University UcinfCL2 papers
- Alexandru Ioan Cuza UniversityRO1 paper
- Arizona State UniversityUS1 paper
- Boston UniversityUS1 paper
- Centre National de la Recherche ScientifiqueFR1 paper
- Chalmers University of TechnologySE1 paper
- Délégation Paris 7FR1 paper
- DePaul UniversityUS1 paper
- Eindhoven University of TechnologyNL1 paper
4 papers · 1 filter
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…
Maximum Matching in Turnstile Streams
Christian Konrad
We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the ins…
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…