ICS 269, Winter 1999: Theory Seminar
4 March 1999:
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.
"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