Algorithms for degree-constrained Euclidean Steiner minimal tree

被引：1

作者：

Jin, Zhang ^{[1
,2
]}

Liang, Ma ^{[1
]}

Zhang Liantang ^{[2
]}

机构：

[1] Shanghai Univ Sci & Technol, Sch Management, Shanghai 200093, Peoples R China

[2] Univ Henan, Comp & Informat Engn Coll, Kaifeng 475001, Peoples R China

来源：

JOURNAL OF SYSTEMS ENGINEERING AND ELECTRONICS | 2008年 / 19卷 / 04期

基金：

中国国家自然科学基金;

关键词：

degree-constrained; Euclidean Steiner minimal tree; simulated annealing; ant algorithm;

D O I：

10.1016/S1004-4132(08)60146-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.

引用

页码：735 / 741

页数：7

共 15 条

[1]

[Anonymous], 1961, CAN MATH BULLETIN, DOI DOI 10.4153/CMB-1961-016-2

[2]

Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892

[3] Ant system: Optimization by a colony of cooperating agents [J].

Dorigo, M ;

Maniezzo, V ;

Colorni, A .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41

[4] Two heuristics for the Euclidean Steiner tree problem [J].

Dreyer, DR ;

Overton, ML .

JOURNAL OF GLOBAL OPTIMIZATION, 1998, 13 (01) :95-106

[5]

DU DZ, 1992, ALGORITHMICA, V7, P121, DOI 10.1007/BF01758755

[6] STEINER MINIMAL TREES [J].

GILBERT, EN ;

POLLAK, HO .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1968, 16 (01) :1-&

[7] A NEW CLASS OF ITERATIVE STEINER TREE HEURISTICS WITH GOOD PERFORMANCE [J].

KAHNG, AB ;

ROBINS, G .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1992, 11 (07) :893-902

[8] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680

[9] A FAST ALGORITHM FOR STEINER TREES [J].

KOU, L ;

MARKOWSKY, G ;

BERMAN, L .

ACTA INFORMATICA, 1981, 15 (02) :141-145

[10] A SURVEY OF SIMULATED ANNEALING APPLICATIONS TO OPERATIONS-RESEARCH PROBLEMS [J].

KOULMAS, C ;

ANTONY, SR ;

JAEN, R .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1994, 22 (01) :41-56

← 1 2 →