Title :
A fast approximation algorithm for maximum-leaf spanning tree
Author :
Lu, Hsueh-I ; Ravi, R.
Author_Institution :
Dept. of Comput. Sci., Nat. Chung-Cheng Univ., Chia-Yi, Taiwan
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)α(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 Ω˜(mn 4)
Keywords :
computational complexity; tree data structures; trees (mathematics); MAX SNP-complete; NP-complete; approximation algorithm; factor-three approximation algorithm; high-order running time; maximum-leaf; spanning tree; Approximation algorithms; Circuits; Computer science; Polynomials; Tree graphs;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1997. (I-SPAN '97) Proceedings., Third International Symposium on
Conference_Location :
Taipei
Print_ISBN :
0-8186-8259-6
DOI :
10.1109/ISPAN.1997.645119