4 papers
Ultrafast Distributed Coloring of High Degree Graphs
Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan
We give a new randomized distributed algorithm for the -list coloring problem. The algorithm and its analysis dramatically simplify the previous best result known of Chang, Li…
Superfast Coloring in CONGEST via Efficient Color Sampling
Magnús M. Halldórsson, Alexandre Nolin
We present a procedure for efficiently sampling colors in the {\congest} model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to s…
Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus +1
Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomiz…
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz
We show that Set Cover on instances with elements cannot be approximated within -factor in time exp(, for any and any , assuming the Expo…