Approximating maximum leaf spanning trees in almost linear time

被引：71

作者：

Lu, HI ^{[1
]}

Ravi, R

机构：

[1] Natl Chung Cheng Univ, Dept CSIE, Tainan, Taiwan

[2] Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA

来源：

JOURNAL OF ALGORITHMS | 1998年 / 29卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.1998.0944

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given an undirected graph, Ending 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)alpha(m, n)) required by our algorithm: where 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.

引用

页码：132 / 141

页数：10

共 14 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Arora S., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P2, DOI 10.1109/SFCS.1992.267824

[3]

Arora S., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P14, DOI 10.1109/SFCS.1992.267823

[4]

BODLAENDER HL, 1989, P WORKSHOP ALGORITHM, P577