37 citations · 142 across the 37 of their papers we have counts for
4 papers · 1 filter
Effective Wireless Scheduling via Hypergraph Sketches
Magnus M. Halldorsson, Tigran Tonoyan
An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available…
Distributed Algorithms for Minimum Degree Spanning Trees
Michael Dinitz, Magnús M. Halldórsson, Calvin Newport
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree for graph with vertices, such that the maximum degree of is t…
Spanning Trees With Edge Conflicts and Wireless Connectivity
Magnus M. Halldorsson, Guy Kortsarz, Pradipta Mitra +1
We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility.…
Simple and Local Independent Set Approximation
Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz
We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach o…