Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-02270-8_30
Title: Approximating the Spanning k-Tree Forest Problem
Authors: Liao, C.-S.
Zhang, L. 
Keywords: Approximation algorithm
K-tree
Spanning forest
Star
Issue Date: 2009
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)
URI: http://scholarbank.nus.edu.sg/handle/10635/104658
ISBN: 3642022693
ISSN: 03029743
DOI: 10.1007/978-3-642-02270-8_30
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Nov 8, 2018

Page view(s)

46
checked on Oct 26, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.