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

DOI10.1016/J.JPDC.2007.07.005zbMATH Open1243.68320arXivcs/0607031OpenAlexW1975151150MaRDI QIDQ436669FDOQ436669

Authors: Christian Lavault, Mario Valencia-Pabon 

Publication date: 26 July 2012

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

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}^{*}$ 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.

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

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
• A time- and message-optimal distributed algorithm for minimum spanning trees

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)

Cites Work

• Title not available (Why is that?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Title not available (Why is that?)
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• 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
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cited In (11)

• Title not available (Why is that?)
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• Minimum-weight spanning tree algorithms. A survey and empirical study
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• From sequential layers to distributed processes
• A linear-time optimal-message distributed algorithm for minimum spanning trees
• A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• 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

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)