A distributed approximation algorithm for the minimum degree minimum weight spanning trees

DOI10.1016/J.JPDC.2007.07.005MaRDI QIDQ436669zbMATHOpenAlexFDO

Authors Christian Lavault, Mario Valencia-Pabon

Publication date 26 July 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsdistributed algorithmsminimum degree minimum weight spanning trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Abstract: Fischer has shown how to compute a minimum weight spanning tree of degree at most $bDelt{a}^{\ast }+lceillo{g}_{b}nceil$ in time $O(n^{4+1/lnb})$ for any constant $b>1$, where $Delt{a}^{\ast }$ is the value of an optimal solution and $n$ is the number of nodes in the network. In this paper, we propose a distributed version of Fischer's algorithm that requires messages and time complexity $O(n^{2+1/lnb})$, and O(n) space per node.

Recommendations

• THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
• Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 732976 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization
• THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS

Cited in

(11)

• From sequential layers to distributed processes
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• Self-stabilizing minimum degree spanning tree within one from the optimal degree
• THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
• A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
• A linear-time optimal-message distributed algorithm for minimum spanning trees
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
• scientific article; zbMATH DE number 1304097 (Why is no real title available?)
• Minimum-weight spanning tree algorithms. A survey and empirical study

This page was built for publication: A distributed approximation algorithm for the minimum degree minimum weight spanning trees

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