Carnegie Mellon University
Browse

Approximating Maximum Leaf Spanning Trees in Almost Linear Time

Download (203.4 kB)
journal contribution
posted on 1974-09-01, 00:00 authored by Hsueh-I Lu, Ramamoorthi RaviRamamoorthi Ravi
Given an undirected graph, finding a spanning tree of the graph with the maximum number of leaves is 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)α(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 that our analysis of the performance of the greedy algorithm is tight via an example.

History

Date

1974-09-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC