Approximating k-hop minimum-spanning trees

0.00 Avg rating—0 Votes

Article ID:	iaor20052285
Country:	Netherlands
Volume:	33
Issue:	2
Start Page Number:	115
End Page Number:	120
Publication Date:	Mar 2005
Journal:	Operations Research Letters
Authors:	Skutella Martin, Knemann Jochen, Althaus Ernst, Funke Stefan, Har-Peled Sariel, Ramos Edgar A.
Keywords:	minimum spanning tree

Abstract:

Given a complete graph on ∼n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in the tree has at most k edges. We present an algorithm that computes such a tree of total expected cost O(log n) times that of a minimum-cost-k-hop spanning-tree.

Reviews

Required fields are marked *. Your email address will not be published.