ICS 269, Winter 1999: Theory Seminar
4 March 1999:
"Approximating Maximum Leaf Spanning Trees in Almost Linear Time"
Journal of Algorithms, Oct. '98 by Hsueh-I Lu & R. Ravi
Speaker: Dave Goggin, ICS, UC Irvine
Abstract: Given an undirected graph, finding a spanning tree of the
graph with the maximum number of leaves in MAX SNP-complete. In
this paper we give a new greedy 3-approximation algorithm for
maximum leaf spanning trees. The running time O((m+n)alpha(m,n))
required by our algorithm, where m is the number of edges and n is
the number of nodes, is almost linear in the size of the graph. We
also demonstrate thatour analysis of the performance of the greedy
algorithm is tight via an example.