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

DOI10.1016/j.jpdc.2007.07.005zbMath1243.68320arXivcs/0607031OpenAlexW1975151150MaRDI QIDQ436669

Mario Valencia-Pabon, Christian Lavault

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)

Related Items

Self-stabilizing minimum degree spanning tree within one from the optimal degree

Cites Work

• Unnamed Item
• Unnamed Item
• THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
• Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization
• 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