Please use this identifier to cite or link to this item:
|Title:||Approximating the Spanning k-Tree Forest Problem|
|Citation:||Liao, C.-S.,Zhang, L. (2009). Approximating the Spanning k-Tree Forest Problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5598 LNCS : 293-301. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-02270-8_30|
|Abstract:||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 k/k+1 in polynomial time for both undirected and directed graphs. In the weighted distance model, a 0.5-approximation algorithm is presented. © 2009 Springer Berlin Heidelberg.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Nov 8, 2018
checked on Oct 26, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.