Parallel algorithms for geometric graph problems

We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a (1 + ε )-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem [9], despite drawing significant attention in recent years.

Authors

• Alexandr Andoni
• Aleksandar Nikolov
• Krzysztof Onak
• Grigory Yaroslavtsev

Keywords

• MapReduce
• earth-mover distance
• minimum spanning tree
• parallel computation