International Journal of Computer Theory and Engineering

Editor-In-Chief: Prof. Mehmet Sahinoglu
Frequency: Quarterly
ISSN: 1793-8201 (Print), 2972-4511 (Online)
Publisher:IACSIT Press
OPEN ACCESS
4.1
CiteScore

⚠️ Important Security Notice: Beware of Fraudulent Emails Impersonating IJCTE Officials
IJCTE 2013 Vol.5(3): 509-513 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2013.V5.739

A Novel Ant Colony Optimization-Based Algorithm for the Optimal Communication Spanning Tree Problem

Nhu Gia Nguyen, Dac-Nhuong Le, and Nguyen Dang Le

Abstract—The optimal communication spanning tree (OCST) problem finds a spanning tree that connects all node satisfies their communication requirements for a minimum total cost. In this paper, we present a new method of finding optimal solution for OCST problem based on Ant Colony Optimization (ACO) to reduce search space mentioned above but still converge to a global good solution. Our algorithm take account into node biased encoding (NBE) scheme to find nearly optimal solution. The new algorithm can achieve a result that is better than known heuristic algorithms do, as verified by a set of public benchmark problem instances.

Index Terms—Optimal communication spanning tree, node biased encoding, ant colony optimization.

Nhu Gia Nguyen is with the Duy Tan University, Danang, Vietnam (e-mail: Nguyengianhu@duytan.edu.vn).
Dac-Nhuong Le is with the Faculty of Information Technology, Haiphong University, Vietnam (e-mail: Nhuongld@ hus.edu.vn).
Nguyen Dang Le is with the Haiphong University, Vietnam (e-mail: Nguyenld@ hus.edu.vn).

[PDF]

Cite:Nhu Gia Nguyen, Dac-Nhuong Le, and Nguyen Dang Le, "A Novel Ant Colony Optimization-Based Algorithm for the Optimal Communication Spanning Tree Problem," International Journal of Computer Theory and Engineering vol. 5, no. 3, pp. 509-513, 2013.

Article Metrics in Dimensions

Menu