2014/06/05 by Alexandra Hochuli, Hochuli, Alexandra, Stephan Holzer +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1406.1244
arxiv created 2014/06/05 · arxiv updated 2014/06/06
We study the NP-hard problem of approximating a Minimum Routing Cost Spanning Tree in the message passing model with limited bandwidth (CONGEST model). In this problem one tries to find a spanning tree of a graph G over n nodes that minimizes the sum of distances between all pairs of nodes. In the considered model every node can transmit a different (but short) message to each of its neighbors in each synchronous round. We provide a randomized (2+ε)-approximation with runtime O(D+\fraclog nε) for unweighted graphs. Here, D is the diameter of G. This improves over both, the (expected) approximation factor O(log n) and the runtime O(Dlog2 n) of the best previously known algorithm. Due to stating our results in a very general way, we also derive an (optimal) runtime of O(D) when considering O(log n)-approximations as done by the best previously known algorithm. In addition we derive a deterministic 2-approximation.