Improved distributed Steiner forest construction

DOI10.1145/2611462.2611464MaRDI QIDQ2943626zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Boaz Patt-Shamir

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2011

zbMATH Keywords

congest modelminimum spanning treenetwork algorithmsSteiner tree

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant $epsilon>0$, a $(2+epsilon)$-approximation in $ildeO(sk+sqrtmin(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(logn)$- approximation in time $ildeO(k+min(s,sqrtn)+D)$, where $D$ is the unweighted diameter of the network. We also prove a matching lower bound of $ildeOmega(k+min(s,sqrtn)+D)$ on the running time of any distributed approximation algorithm for the Steiner Forest problem. Previous algorithms were randomized, and obtained either an $O(logn)$-approximation in $ildeO(sk)$ time, or an $O(1/epsilon)$-approximation in $ildeO((sqrtn+t{)}^{1+epsilon}+D)$ time.

Recommendations

• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Computing and Combinatorics
• Distributed algorithms for low stretch spanning trees
• A primal-dual approximation algorithm for the Steiner forest problem
• The Steiner problem in distributed computing systems

Cited in

(9)

• Fast distributed approximation for TAP and 2-edge-connectivity
• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed distance computation and routing with small messages
• Fast distributed approximation for TAP and 2-edge-connectivity
• Exact bounds for distributed graph colouring
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Massively parallel approximate Steiner tree algorithms
• Distributed model checking on graphs of bounded treedepth

This page was built for publication: Improved distributed Steiner forest construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943626)