Ant system for the k-cardinality tree problem

Thang N. Bui; Gnanasekaran Sundarraj

doi:10.1007/978-3-540-24854-5_4

Ant system for the k-cardinality tree problem

Thang N. Bui, Gnanasekaran Sundarraj

School of Science, Engineering & Technology (Harrisburg)

Research output: Chapter in Book/Report/Conference proceeding › Chapter

9 Scopus citations

Abstract

This paper gives an algorithm for finding the minimum weight tree having k edges in an edge weighted graph. The algorithm combines a search and optimization technique based on pheromone with a weight based greedy local optimization. Experimental results on a large set of problem instances show that this algorithm matches or surpasses other algorithms including an ant colony optimization algorithm, a tabu search algorithm, an evolutionary algorithm and a greedy-based algorithm on all but one of the 138 tested instances.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Kalyanmoy Deb, Riccardo Poli, Owen Holland, Kalyanmoy Banzhaf, Hans-Georg Beyer, Edmund Burke, Paul Darwen, Dipankar Dasgupta, Dario Floreano, James Foster, Mark Harman, Pier Luca Lanzi, Lee Spector, Andrea G. B. Tettamanzi, Dirk Thierens, Andrew M. Tyrrell
Publisher	Springer Verlag
Pages	36-47
Number of pages	12
ISBN (Print)	3540223444, 9783540223443
DOIs	https://doi.org/10.1007/978-3-540-24854-5_4
State	Published - 2004

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3102
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-24854-5_4

Cite this

Bui, T. N., & Sundarraj, G. (2004). Ant system for the k-cardinality tree problem. In K. Deb, R. Poli, O. Holland, K. Banzhaf, H.-G. Beyer, E. Burke, P. Darwen, D. Dasgupta, D. Floreano, J. Foster, M. Harman, P. L. Lanzi, L. Spector, A. G. B. Tettamanzi, D. Thierens, & A. M. Tyrrell (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 36-47). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3102). Springer Verlag. https://doi.org/10.1007/978-3-540-24854-5_4

Bui, Thang N. ; Sundarraj, Gnanasekaran. / Ant system for the k-cardinality tree problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Kalyanmoy Deb ; Riccardo Poli ; Owen Holland ; Kalyanmoy Banzhaf ; Hans-Georg Beyer ; Edmund Burke ; Paul Darwen ; Dipankar Dasgupta ; Dario Floreano ; James Foster ; Mark Harman ; Pier Luca Lanzi ; Lee Spector ; Andrea G. B. Tettamanzi ; Dirk Thierens ; Andrew M. Tyrrell. Springer Verlag, 2004. pp. 36-47 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{021253205aac4720b49befd3142dbf4e,

title = "Ant system for the k-cardinality tree problem",

abstract = "This paper gives an algorithm for finding the minimum weight tree having k edges in an edge weighted graph. The algorithm combines a search and optimization technique based on pheromone with a weight based greedy local optimization. Experimental results on a large set of problem instances show that this algorithm matches or surpasses other algorithms including an ant colony optimization algorithm, a tabu search algorithm, an evolutionary algorithm and a greedy-based algorithm on all but one of the 138 tested instances.",

author = "Bui, {Thang N.} and Gnanasekaran Sundarraj",

year = "2004",

doi = "10.1007/978-3-540-24854-5_4",

language = "English (US)",

isbn = "3540223444",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "36--47",

editor = "Kalyanmoy Deb and Riccardo Poli and Owen Holland and Kalyanmoy Banzhaf and Hans-Georg Beyer and Edmund Burke and Paul Darwen and Dipankar Dasgupta and Dario Floreano and James Foster and Mark Harman and Lanzi, {Pier Luca} and Lee Spector and Tettamanzi, {Andrea G. B.} and Dirk Thierens and Tyrrell, {Andrew M.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Bui, TN & Sundarraj, G 2004, Ant system for the k-cardinality tree problem. in K Deb, R Poli, O Holland, K Banzhaf, H-G Beyer, E Burke, P Darwen, D Dasgupta, D Floreano, J Foster, M Harman, PL Lanzi, L Spector, AGB Tettamanzi, D Thierens & AM Tyrrell (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3102, Springer Verlag, pp. 36-47. https://doi.org/10.1007/978-3-540-24854-5_4

Ant system for the k-cardinality tree problem. / Bui, Thang N.; Sundarraj, Gnanasekaran.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Kalyanmoy Deb; Riccardo Poli; Owen Holland; Kalyanmoy Banzhaf; Hans-Georg Beyer; Edmund Burke; Paul Darwen; Dipankar Dasgupta; Dario Floreano; James Foster; Mark Harman; Pier Luca Lanzi; Lee Spector; Andrea G. B. Tettamanzi; Dirk Thierens; Andrew M. Tyrrell. Springer Verlag, 2004. p. 36-47 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3102).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Ant system for the k-cardinality tree problem

AU - Bui, Thang N.

AU - Sundarraj, Gnanasekaran

PY - 2004

Y1 - 2004

N2 - This paper gives an algorithm for finding the minimum weight tree having k edges in an edge weighted graph. The algorithm combines a search and optimization technique based on pheromone with a weight based greedy local optimization. Experimental results on a large set of problem instances show that this algorithm matches or surpasses other algorithms including an ant colony optimization algorithm, a tabu search algorithm, an evolutionary algorithm and a greedy-based algorithm on all but one of the 138 tested instances.

AB - This paper gives an algorithm for finding the minimum weight tree having k edges in an edge weighted graph. The algorithm combines a search and optimization technique based on pheromone with a weight based greedy local optimization. Experimental results on a large set of problem instances show that this algorithm matches or surpasses other algorithms including an ant colony optimization algorithm, a tabu search algorithm, an evolutionary algorithm and a greedy-based algorithm on all but one of the 138 tested instances.

UR - http://www.scopus.com/inward/record.url?scp=33750279119&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750279119&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24854-5_4

DO - 10.1007/978-3-540-24854-5_4

M3 - Chapter

AN - SCOPUS:33750279119

SN - 3540223444

SN - 9783540223443

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 36

EP - 47

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Deb, Kalyanmoy

A2 - Poli, Riccardo

A2 - Holland, Owen

A2 - Banzhaf, Kalyanmoy

A2 - Beyer, Hans-Georg

A2 - Burke, Edmund

A2 - Darwen, Paul

A2 - Dasgupta, Dipankar

A2 - Floreano, Dario

A2 - Foster, James

A2 - Harman, Mark

A2 - Lanzi, Pier Luca

A2 - Spector, Lee

A2 - Tettamanzi, Andrea G. B.

A2 - Thierens, Dirk

A2 - Tyrrell, Andrew M.

PB - Springer Verlag

ER -

Bui TN, Sundarraj G. Ant system for the k-cardinality tree problem. In Deb K, Poli R, Holland O, Banzhaf K, Beyer HG, Burke E, Darwen P, Dasgupta D, Floreano D, Foster J, Harman M, Lanzi PL, Spector L, Tettamanzi AGB, Thierens D, Tyrrell AM, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 36-47. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-24854-5_4

Ant system for the k-cardinality tree problem

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this