Artificial immune system to find a set of k-spanning trees with low costs and distinct topologies
Authors: 
Priscila C. Berbert, Leonardo J. R. Freitas Filho, 
Tiago A. Almeida, Márcia B. Carvalho, Akebo YamakamiAuthors Info & Claims
Pages 395 - 406
Abstract
This work proposes an Artificial Immune System to find a set of k spanning trees with low costs and distinct topologies. The attainment of this set of solutions is necessary when the problem has restrictions or when the interest is to present good alternative solutions for posterior decision making. Solving this problem means to explore an enormous space of solutions that grows as the number of graph nodes increases; it becomes impractible using exact or comparative methods. However, it is known that bio-inspired algorithms have a high capacity of exploration and exploitation of the search space. Moreover, inherent characteristics of AIS become the search mechanism more efficient allowing the resolution of this problem in a feasible computational time.
References
[1]
Ahuja, R.K., Magnati, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications, 1st edn. Prentice-Hall, United States (1993).
[2]
Ali, M., Ramamurthy, B., Deogun, J.S.: Routing and Wavelength Assignment with Power Considerations in Optical Networks. Computer Networks 32, 539-555 (2000).
[3]
Almeida, T.A., Yamakami, A.: Evolutionary Computation Applied to Solve the Minimum Spanning Tree Problem with Fuzzy Parameters. Master Thesis, School of Electrical and Computing Engineering, State University of Campinas 2006 (in Portuguese).
[4]
Coello Coello, C.A., Cortés, N.C.: Solving Multiobjective Optimization Problems Using an Artificial Immune System. Genetic Programming and Evolvable Machines 6, 163-190 (2005).
[5]
Dasgupta, D.: Artificial Immune Systems and Their Applications, 1st edn. Springer, Nova York (1998).
[6]
De Castro, L.N., Von Zuben, F.J.: Immune Engineering: Development and Application of Computational Tools Inspired in Artificial Immune Systems. PhD Thesis, State University of Campinas, School of Electrical and Computing Engineering 2001 (in Portuguese).
[7]
Keko, H., Skok, M., Skrlec, D.: Artificial Immune Systems in Solving Routing Problems. Computer as Tool. In: EUROCON 2003. Computer as Tool, The IEEE Region, vol. 8(1), pp. 62-66 (2003).
[8]
Lederberg, J.: Ontogeny of the Clonal Selection Theory of Antibody Formation. Annals of the New York Ac. of Sc. 546, 175-182 (1988).
[9]
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd edn. Springer, Heidelberg (1996).
[10]
Minty, G.J.: A Simple Algorithm for Listing All the Trees of a Graph. IEEE Transactions on Circuit Theory CT-12, 120 (1965).
[11]
Murty, K.G.: An Algorithm for Ranking All the Assignments in Order of Increasing Cost. Operations Research 16, 682-687 (1986).
[12]
Okada, S.: Interactions Among Paths in Fuzzy Shortest Path Problems. In: Proceedings of the 9th International Fuzzy Systems Associations World Congress, pp. 41-46 (2001).
[13]
Raidl, R.G., Julstrom, B.A.: Edge-Sets: An Effective Evolutionary Coding of Spanning Trees. Research Report, Vienna University of Technology, Institute of Computer Graphics and Algorithms (2001).
[14]
Sörensen, K., Janssens, G.K.: An Algorithm to Generate All Spanning Trees of a Graph in Order of Increasing Cost. Operational Research 25, 219-229 (2005).
Index Terms
- Artificial immune system to find a set of k-spanning trees with low costs and distinct topologies
Index terms have been assigned to the content through auto-classification.
Recommendations
Low-Degree Spanning Trees of Small Weight
Given $n$ points in the plane, the degree-$K$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $K$. This paper addresses the problem of computing low-weight degree-$K$ spanning trees for $K>2$...
Node-independent spanning trees in Gaussian networks
Message broadcasting in networks can be efficiently carried over spanning trees. A set of spanning trees in the same network is node independent if two conditions are satisfied. First, all trees are rooted at the same node r. Second, for every node u in ...
Degree-bounded minimum spanning trees
Given n points in the Euclidean plane, the degree-@d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most @d. The problem is NP-hard for 2@__ __@d@__ __3, while the NP-hardness of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2007
437 pages
ISBN:3540739211
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 26 August 2007
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 2Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024