Another greedy heuristic for the constrained forest problem

被引：7

作者：

Laszlo, M ^{[1
]}

Mukherjee, S ^{[1
]}

机构：

[1] Nova SE Univ, Grad Sch Comp & Informat Sci, Ft Lauderdale, FL 33314 USA

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 06期

关键词：

constrained forest problem; tree partitioning; minimum spanning forests; greedy heuristics;

D O I：

10.1016/j.orl.2004.11.010

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a greedy heuristic for this NP-hard problem, whose solutions are at least as good as, and often better than, those produced by the best-known 2-approximate heuristic. (c) 2004 Elsevier B.V. All rights reserved.

引用

页码：629 / 633

页数：5

共 6 条

[1] On the complexity of graph tree partition problems [J].

Cordone, R ;

Maffioli, F .

DISCRETE APPLIED MATHEMATICS, 2004, 134 (1-3) :51-65

[2]

DANDEKAR RA, 2002, LECT NOTES COMPUTER, V2316

[3] Practical data-oriented microaggregation for statistical disclosure control [J].

Domingo-Ferrer, J ;

Mateo-Sanz, JM .

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2002, 14 (01) :189-201

[4]

IMELINSKA C, 1993, OPER RES LETT, V14, P65

[5] An efficient k-means clustering algorithm:: Analysis and implementation [J].

Kanungo, T ;

Mount, DM ;

Netanyahu, NS ;

Piatko, CD ;

Silverman, R ;

Wu, AY .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2002, 24 (07) :881-892

[6]

LASZLO M, MINIMUM SPANNING TRE

← 1 →