International Journal of Computational Intelligence Research

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

An Empirical Study on Crossover Operator for Degree Constraint Minimal Spanning Tree Problem Using Genetic Algorithm


Affiliations
1 Department of Master of Computer Applications, M.S. Engineering College, Bangalore, India
2 Faculty of Computer Studies Kadi Sarva Vishwavidyalya, Gandhinagar, India
     

   Subscribe/Renew Journal


This paper presents an influence of crossover operator in genetic algorithm for small to large minimum spanning tree problem. A minimum spanning tree problem becomes NP-hard problem when additional constraint degree is applied with each node to restrict the number of edges. Crossover operator plays an important role in genetic algorithm approach. Since many researchers have tried to solve this problem for small to mid size, we have explored the use of genetic algorithm with various crossover functions with modification but without changing the nature of genetic algorithm. Various crossover functions have been developed here as per the requirement of the problem and applied with the various size of network. In this paper we have tried to show the impact of crossover function in genetic algorithm.

Keywords

Genetic Algorithm, Crossover Operator Degree Constrained Minimum Spanning Tree
Subscription Login to verify subscription
User
Notifications
Font Size


  • F. Harary and J. P. Hayes, “Node fault tolerance in graphs,” Networks, vol. 27, no. 1, pp. 19–23, 1996

  • H. K. Ku and J. P. Hayes, “Optimally edge fault-tolerant trees,” Networks, vol. 27, no. 3, pp. 203–214, 1996.

  • Cunha, A. and A. Lucena, “Algorithms for the degree-constrained minimum spanning tree problem,” Electronic Notes in Discrete Mathematics, volume 19, pages 403-409, and 2005

  • Narsingh Deo, 2000. Graph Theory with Applications to Engineering and Computer science: (PHI)

  • A Novel Genetic Algorithm approach for Network Design wit Robust Fitness Function International Journal of Computer Theory and Engineering, Vol. 2, No. 3, June, 20101793-8201

  • Melanie M. (1998). An Introduction to genetic Algorithm (PHI ) ISBN 81- 203-1385-5

  • Michael D. Vose. 1999. The simple genetic algorithm : (PHI) ISBN 61-203- 2459-5

  • Lixia Hanr and Yuping Wang, A Novel Genetic Algorithm for Degree- Constrained Minimum Spanning Tree Problem, IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.7A, July 2006


Abstract Views: 276

PDF Views: 0




  • An Empirical Study on Crossover Operator for Degree Constraint Minimal Spanning Tree Problem Using Genetic Algorithm

Abstract Views: 276  |  PDF Views: 0

Authors

Anand Kumar
Department of Master of Computer Applications, M.S. Engineering College, Bangalore, India
N.N. Jani
Faculty of Computer Studies Kadi Sarva Vishwavidyalya, Gandhinagar, India

Abstract


This paper presents an influence of crossover operator in genetic algorithm for small to large minimum spanning tree problem. A minimum spanning tree problem becomes NP-hard problem when additional constraint degree is applied with each node to restrict the number of edges. Crossover operator plays an important role in genetic algorithm approach. Since many researchers have tried to solve this problem for small to mid size, we have explored the use of genetic algorithm with various crossover functions with modification but without changing the nature of genetic algorithm. Various crossover functions have been developed here as per the requirement of the problem and applied with the various size of network. In this paper we have tried to show the impact of crossover function in genetic algorithm.

Keywords


Genetic Algorithm, Crossover Operator Degree Constrained Minimum Spanning Tree

References