An ant colony optimization approach to the degree-constrained minimum spanning tree problem
This paper presents the application of an Ant Colony Optimization (ACO) algorithm approach for communications networks design problem. We explore the use of ACO's for solving a network optimization problem, the degree-constrained minimum spanning tree problem (d-MST), which is a NP-Hard problem...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/2300/ |
| _version_ | 1848790019222798336 |
|---|---|
| author | Ewe, HT Ho, , CK Bau, , YT |
| author_facet | Ewe, HT Ho, , CK Bau, , YT |
| author_sort | Ewe, HT |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | This paper presents the application of an Ant Colony Optimization (ACO) algorithm approach for communications networks design problem. We explore the use of ACO's for solving a network optimization problem, the degree-constrained minimum spanning tree problem (d-MST), which is a NP-Hard problem. The effectiveness of the proposed algorithm is demonstrated through two kinds of data set: structured hard (SHRD) complete graphs and misleading (M-graph) complete graphs. Empirical results show that ACO performs competitively with other approaches based on evolutionary algorithm (EA) on certain instance set problem. |
| first_indexed | 2025-11-14T18:05:57Z |
| format | Article |
| id | mmu-2300 |
| institution | Multimedia University |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:05:57Z |
| publishDate | 2005 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-23002011-08-24T06:12:25Z http://shdl.mmu.edu.my/2300/ An ant colony optimization approach to the degree-constrained minimum spanning tree problem Ewe, HT Ho, , CK Bau, , YT QA75.5-76.95 Electronic computers. Computer science This paper presents the application of an Ant Colony Optimization (ACO) algorithm approach for communications networks design problem. We explore the use of ACO's for solving a network optimization problem, the degree-constrained minimum spanning tree problem (d-MST), which is a NP-Hard problem. The effectiveness of the proposed algorithm is demonstrated through two kinds of data set: structured hard (SHRD) complete graphs and misleading (M-graph) complete graphs. Empirical results show that ACO performs competitively with other approaches based on evolutionary algorithm (EA) on certain instance set problem. 2005 Article NonPeerReviewed Ewe, HT and Ho, , CK and Bau, , YT (2005) An ant colony optimization approach to the degree-constrained minimum spanning tree problem. COMPUTATIONAL INTELLIGENCE AND SECURITY, PT 1, PROCEEDINGS, 3801 . pp. 657-662. ISSN 0302-9743 |
| spellingShingle | QA75.5-76.95 Electronic computers. Computer science Ewe, HT Ho, , CK Bau, , YT An ant colony optimization approach to the degree-constrained minimum spanning tree problem |
| title | An ant colony optimization approach to the degree-constrained minimum spanning tree problem |
| title_full | An ant colony optimization approach to the degree-constrained minimum spanning tree problem |
| title_fullStr | An ant colony optimization approach to the degree-constrained minimum spanning tree problem |
| title_full_unstemmed | An ant colony optimization approach to the degree-constrained minimum spanning tree problem |
| title_short | An ant colony optimization approach to the degree-constrained minimum spanning tree problem |
| title_sort | ant colony optimization approach to the degree-constrained minimum spanning tree problem |
| topic | QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/2300/ |