A fast approximation algorithm for maximum-leaf spanning tree
Journal
3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997
Pages
351-356
Date Issued
1997
Author(s)
Lu, H.-I.
HSUEH-I LU
Abstract
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete but also MAX SNP-complete. The approximation ratio of the previously best known approximation algorithm for maximum leaf spanning tree is three. However, the high-order running time required by the previous algorithm makes it impractical. In this paper we give a new factor-three approximation algorithm for the same problem. The running time O((m+n)/spl alpha/(m, n)) required by our algorithm is almost linear in the size of G, where m is the number of edged and n is the number of nodes. This improves the previous algorithm by a factor of /spl Omega//spl tilde/(mn/sup 4/).
Type
conference paper