Distributed approximation of minimum routing cost trees

DOI10.1007/978-3-319-09620-9_11MaRDI QIDQ5496154zbMATH OpenOpenAlexFDO

Authors Alexandra Hochuli, Stephan Holzer, Roger Wattenhofer

Publication date 7 August 2014

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: 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+epsilon)$-approximation with runtime $O(D+fraclognepsilon)$ for unweighted graphs. Here, $D$ is the diameter of $G$. This improves over both, the (expected) approximation factor $O(logn)$ and the runtime $O(Dlo{g}^{2}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(logn)$-approximations as done by the best previously known algorithm. In addition we derive a deterministic $2$-approximation.

Recommendations

• scientific article; zbMATH DE number 1303537
• A fast algorithm for computing minimum routing cost spanning trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Computing and Combinatorics
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees

Cited in

(9)

• Minimizing broadcast costs under edge reductions in tree networks
• The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm
• On the minimum routing cost clustered tree problem
• A fast algorithm for computing minimum routing cost spanning trees
• Distributed computing of efficient routing schemes in generalized chordal graphs
• Light graphs with small routing cost
• Decentralized pricing in minimum cost spanning trees
• Size-constrained tree partitioning: approximating the multicast k-tree routing problem
• Parameterized algorithms for computing MAD trees

This page was built for publication: Distributed approximation of minimum routing cost trees

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