An exact algorithm for the maximum leaf spanning tree problem

被引：47

作者：

Fujie, T ^{[1
]}

机构：

[1] Kobe Univ Commerce, Dept Management Sci, Nishi Ku, Kobe, Hyogo 6512197, Japan

来源：

COMPUTERS & OPERATIONS RESEARCH | 2003年 / 30卷 / 13期

关键词：

branch and bound; spanning trees; integer programming;

D O I：

10.1016/S0305-0548(02)00117-X

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Given a connected graph, the Maximum Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree whose number of leaves (degree-one vertices) is maximum. We propose a branch-and-bound algorithm for MLSTP, in which an upper bound is obtained by solving a minimum spanning tree problem. We report computational results for randomly generated graphs and grid graphs with up to 100 vertices.

引用

页码：1931 / 1944

页数：14

共 14 条

[1]

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

[2]

[Anonymous], P 4 ANN EUR S ALG

[3] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[4] Minimal spanning trees with a constraint on the number of leaves [J].

Fernandes, LM ;

Gouveia, L .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 104 (01) :250-261

[5]

FUJIE T, 1998, MAXIMUM LEAF SPANNIN

[6] A SHORT NOTE ON THE APPROXIMABILITY OF THE MAXIMUM LEAVES SPANNING TREE PROBLEM [J].

GALBIATI, G ;

MAFFIOLI, F ;

MORZENTI, A .

INFORMATION PROCESSING LETTERS, 1994, 52 (01) :45-49

[7]

Geoffrion A, 1974, MATHEMATICAL PROGRAM, V2, P82, DOI DOI 10.1007/BFB0120690

[8] SPANNING-TREES WITH MANY LEAVES [J].

KLEITMAN, DJ ;

WEST, DB .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1991, 4 (01) :99-106

[9]

Lu H, 1992, P 30 ANN ALL C COMM, P533

[10] Approximating maximum leaf spanning trees in almost linear time [J].

Lu, HI ;

Ravi, R .

JOURNAL OF ALGORITHMS, 1998, 29 (01) :132-141

← 1 2 →