Can I read Towards Distributed 2-Approximation Steiner Minimal Trees in Billion-edge Graphs on EtoBox?

Towards Distributed 2-Approximation Steiner Minimal Trees in Billion-edge Graphs by Reza, Tahsin; Sanders, Geoffrey; Pearce, Roger is a scholarly article available to read on EtoBox.

What is Towards Distributed 2-Approximation Steiner Minimal Trees in Billion-edge Graphs about?

Given an edge-weighted graph and a set of known seed vertices, a network scientist often desires to understand the graph relationships to explain connections between the seed vertices. When the seed set is 3 or larger Steiner minimal tree - min-weight acyclic connected subgraph (of the input graph) that contains all the seed vertices - is an attractive generalization of shortest weighted paths. In general, computing a Steiner minimal tree is NP-hard, but several polynomial-time algorithms have been designed and proven to yield Steiner trees whose total weight is bounded within 2 times the Steiner minimal tree. In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of distance computation between all pairs of seed vertices, an expensive phase in many algorithms, our solution exploits Voronoi cell computation. Also, this approach has higher parallel efficiency than others that involve minimum spanning tree computation on the entire graph. Furthermore, our distributed design exploits asynchronous processing and a message prioritization scheme to accelerate convergence of distance computation, and harne

Author

Reza, Tahsin; Sanders, Geoffrey; Pearce, Roger

Published

2022

Language

EN