TY - GEN
T1 - Ant colony optimization applied to minimum weight dominating set problem
AU - Jovanovic, Raka
AU - Tuba, Milan
AU - Simian, Dana
PY - 2010
Y1 - 2010
N2 - In this paper we present an application of ant colony optimization (ACO) to the Minimum Weighted Dominating Set Problem. We introduce a heuristic for this problem that takes into account the weights of vertexes being covered and show that it is more efficient than the greedy algorithm using the standard heuristic. Further we give implementation details of ACO applied to this problem. We tested our algorithm on graphs with different sizes, edge densities, and weight distribution functions and shown that it gives greatly improved results over these acquired by the greedy algorithms.
AB - In this paper we present an application of ant colony optimization (ACO) to the Minimum Weighted Dominating Set Problem. We introduce a heuristic for this problem that takes into account the weights of vertexes being covered and show that it is more efficient than the greedy algorithm using the standard heuristic. Further we give implementation details of ACO applied to this problem. We tested our algorithm on graphs with different sizes, edge densities, and weight distribution functions and shown that it gives greatly improved results over these acquired by the greedy algorithms.
KW - Ant colony optimization
KW - Dominating set problem
KW - Optimization problems
KW - Population based algorithms
UR - http://www.scopus.com/inward/record.url?scp=79952633691&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:79952633691
SN - 9789549260014
T3 - 12th WSEAS International Conference on Automatic Control, Modelling and Simulation, ACMOS '10
SP - 322
EP - 326
BT - 12th WSEAS International Conference on Automatic Control, Modelling and Simulation, ACMOS '10
T2 - 12th WSEAS International Conference on Automatic Control, Modelling and Simulation, ACMOS '10
Y2 - 29 May 2010 through 31 May 2010
ER -