Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Approximating the Spanning k-Tree Forest Problem
verfasst von : Chung-Shou Liao, Louxin Zhang
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
As a generalization of the spanning star forest problem, the spanning
k
-tree forest problem is to find a maximum-edge-weight spanning forest in which each tree has a central node and other nodes in the tree are at most
k
-distance away from the central node. In this paper, we show that it can be approximated with ratio
$\frac{k}{k+1}$
in polynomial time for both undirected and directed graphs. In the weighted distance model, a 0.5-approximation algorithm is presented.