Solving the Degree-Constrained Euclidean Steiner Minimal Tree Problem

Shu Juan Dong

doi:10.4028/www.scientific.net/AMR.219-220.652

Paper Titles

Analysis of Collected Heat by Solar Collectors Fixed on the Outside Wall of Balcony
p.633

A New Model for Web Service Composition
p.638

Application of Multi-Dimensional Analysis Technology in Telecom Industry
p.643

The Building of Offshore Facilities Power System’s Equivalent Circuit Model
p.648

Solving the Degree-Constrained Euclidean Steiner Minimal Tree Problem
p.652

Study on the Forecasting Method of Grain Potential Productivity of Heilongjiang Province
p.656

Experimental Study on the Shear Strength Characteristics of Municipal Solid Waste
p.660

A Design and Implementation of Comprehensive MPEG-2 Transport Stream Analysis System for Large-Scale TV Station
p.665

Interferometer Environmental Error Compensation Based on Refractive Index’s Spatio-Temporal Coupling Model
p.670

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 219-220Solving the Degree-Constrained Euclidean Steiner...

Solving the Degree-Constrained Euclidean Steiner Minimal Tree Problem

Abstract:

The degree-constrained Euclidean Steiner minimal tree problem was discussed based on the Euclidean Steiner minimal tree with each original point being added with a degree constraint. The property of the problem was analyzed and the implementation process of solving the problem by using the simulated annealing algorithm and the ant algorithm was presented. Both algorithms are coded in Delphi and run on the Windows XP environment. Series of numerical examples were tested and the efficiency of these algorithms was validated.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 219-220)

Pages:

652-655

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.219-220.652

Citation:

Cite this paper

Online since:

March 2011

Authors:

Shu Juan Dong

Keywords:

Algorithm (GA), DCESMT, Degree-Constrained, Mathematical Models

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] GAREYM, JOHNSONDS. The rectilinear Steiner problem is NP -complete[J]. SIAM Journal on Applied Mathematics, 1977,32 (6) :826-834.

DOI: 10.1137/0132071

Google Scholar

[2] NARULASC, HOCA. Degree-constrained minimum spanning tree[J]. Computers and Operations Research, 1980,7 (4) :239-249.

DOI: 10.1016/0305-0548(80)90022-2

Google Scholar

[3] MaLiang, JiangFu. Fast algorithm for the degree-constrained minimum spanning tree[J]. Operations research and management science, 1998,7 (1) :1-5.

Google Scholar

[4] DORIGOM, MANIEZZOV, COLORNIA. Ant system: Optimization by acolony of cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, PartB, 1996,26 (1) :29-41.

Google Scholar

[5] MaLiang, JiangFu. Ant algorithm for the degree-constrained minimum spanning tree[J]. Journal of systems engineering , 1999,14 (3) :211-214.

Google Scholar

[6] JinHuimin, MaLiang, WangZhoumian. Intelligent optimization algorithms for Euclidean Steiner minimum tree problem[J]. Computer Engineering, 2006,32 (10) :201-203.

Google Scholar