2014/05/08 by Lenzen, Christoph, Patt-Shamir, Boaz
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1405.2011
We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant ε>0, a (2+ε)-approximation in O(sk+√(min(st,n))) rounds, where s is the shortest path diameter, t is the number of terminals, k is the number of terminal components in the input, and n is the number of nodes. Our randomized algorithm finds, with high probability, an O(log n)- approximation in time O(k+min(s,√ n)+D), where D is the unweighted diameter of the network. We also prove a matching lower bound of Ω(k+min(s,√(n))+D) on the running time of any distributed approximation algorithm for the Steiner Forest problem. Previous algorithms were randomized, and obtained either an O(log n)-approximation in O(sk) time, or an O(1/ε)-approximation in O((√(n)+t)1+ε+D) time.