ICS Theory Group

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.