TY - GEN
T1 - An ant-based algorithm for finding degree-constrained minimum spanning tree
AU - Bui, Thang N.
AU - Zrncic, Catherine M.
PY - 2006
Y1 - 2006
N2 - A spanning tree of a graph such that each vertex in the tree has degree at most d is called a degree-constrained spanning tree. The problem of finding the degree-constrained spanning tree of minimum cost in an edge weighted graph is well known to be NP-hard. In this paper we give an Ant-Based algorithm for finding low cost degree-constrained spanning trees. Ants are used to identify a set of candidate edges from which a degree-constrained spanning tree can be constructed. Extensive experimental results show that the algorithm performs very well against other algorithms on a set of 572 problem instances.
AB - A spanning tree of a graph such that each vertex in the tree has degree at most d is called a degree-constrained spanning tree. The problem of finding the degree-constrained spanning tree of minimum cost in an edge weighted graph is well known to be NP-hard. In this paper we give an Ant-Based algorithm for finding low cost degree-constrained spanning trees. Ants are used to identify a set of candidate edges from which a degree-constrained spanning tree can be constructed. Extensive experimental results show that the algorithm performs very well against other algorithms on a set of 572 problem instances.
UR - http://www.scopus.com/inward/record.url?scp=33750225376&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33750225376&partnerID=8YFLogxK
U2 - 10.1145/1143997.1144000
DO - 10.1145/1143997.1144000
M3 - Conference contribution
AN - SCOPUS:33750225376
SN - 1595931864
SN - 9781595931863
T3 - GECCO 2006 - Genetic and Evolutionary Computation Conference
SP - 11
EP - 18
BT - GECCO 2006 - Genetic and Evolutionary Computation Conference
PB - Association for Computing Machinery
T2 - 8th Annual Genetic and Evolutionary Computation Conference 2006
Y2 - 8 July 2006 through 12 July 2006
ER -