APPROXIMATING MAXIMUM LEAF SPANNING-TREES IN ALMOST LINEAR-TIME

Authors
LU HI RAVI R
Citation
Hi. Lu et R. Ravi, APPROXIMATING MAXIMUM LEAF SPANNING-TREES IN ALMOST LINEAR-TIME, Journal of algorithms (Print), 29(1), 1998, pp. 132-141
Citations number
14
Categorie Soggetti
Mathematics,"Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms (Print) → ACNP
ISSN journal
01966774
Volume
29
Issue
1
Year of publication
1998
Pages
132 - 141
Database
ISI
SICI code
0196-6774(1998)29:1<132:AMLSIA>2.0.ZU;2-0
Abstract
Given an undirected graph, Ending a spanning tree of the graph with th e 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)alpha(m, n)) required by our algorithm: wh ere nt 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, ( C) 1998 Academic Press.