| Autor: |
Alok Singh, Ramana Murthy V. Venkata |
| Rok vydání: |
2012 |
| Předmět: |
|
| Zdroj: |
2012 2nd IEEE International Conference on Parallel, Distributed and Grid Computing. |
| DOI: |
10.1109/pdgc.2012.6449909 |
| Popis: |
The min-degree constrained minimum spanning tree (MDCMST) problem seeks a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least d in the tree. MDCMST problem is NP-Hard. In this paper we have proposed a new heuristic and a metaheuristic approach to this problem. The metaheuristic approach consists of a recently proposed swarm intelligence technique called artificial bee colony algorithm. The proposed approaches have been tested on Euclidean and random instances both. For small values of d, the heuristic and ABC approach perform quite similar. However, advantage of ABC approach becomes clearly visible for larger values of d. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
