We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
An Efficient Restoration Method for the Faint Dot Matrix Images

Ao Zhu Peng Cao
Random Articles
Reseach Article

A Quantum Differential Evolutionary Algorithm for the Independent Set Problem

by Omar Kettani, Faycal Ramdani, Benaissa Tadili
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 58 - Number 14
Year of Publication: 2012
Authors: Omar Kettani, Faycal Ramdani, Benaissa Tadili
10.5120/9353-3685

Omar Kettani, Faycal Ramdani, Benaissa Tadili . A Quantum Differential Evolutionary Algorithm for the Independent Set Problem. International Journal of Computer Applications. 58, 14 ( November 2012), 39-42. DOI=10.5120/9353-3685

@article{ 10.5120/9353-3685,
author = { Omar Kettani, Faycal Ramdani, Benaissa Tadili },
title = { A Quantum Differential Evolutionary Algorithm for the Independent Set Problem },
journal = { International Journal of Computer Applications },
issue_date = { November 2012 },
volume = { 58 },
number = { 14 },
month = { November },
year = { 2012 },
issn = { 0975-8887 },
pages = { 39-42 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume58/number14/9353-3685/ },
doi = { 10.5120/9353-3685 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:02:32.582283+05:30
%A Omar Kettani
%A Faycal Ramdani
%A Benaissa Tadili
%T A Quantum Differential Evolutionary Algorithm for the Independent Set Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 58
%N 14
%P 39-42
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Independent Set problem consists to find a maximum cardinality subset of vertices of a given graph such that no two vertices are adjacent. In this paper, we propose a quantum evolutionary algorithm which uses a differential operator to update the quantum angles of the superposition state of Q-bits for solving this problem. Simulation results on some graph examples show that this approach is effective.

References
  1. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory NP-completeness, San Francisco:Freeman (1979).
  2. R. Mosca, "Polynomial algorithms for the maximum stable set problem on particular classes of P5-free graphs,"Information Processing Letters,61, 1997, pp. 137-143.
  3. A. Brandstädt, C. T. Hoàng, V. B. Le, "Stability number of bull-and chair-free graphs revisited," Discrete Appl. Math. 131 (2003) 39–50.
  4. P. Benioff, The computer as a physical system: a microscopic quantum mechanical hamiltonian model of computers as represented by Turing machines, J. Stat. Phys. 22 (1980) 563–591.
  5. B. Jiao, X. Gu and G. Xu, "An Improved Quantum Differential Algorithm for Stochastic Flow Shop Scheduling Problem". In Proc. IEEE International Conference on Control and Automation 2009,pp. 1235-1240.
  6. A. Draa , S. Meshoul, H. Talbi and M. Batouche, "A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem". The International Arab Journal of Information Technology,Vol. 7, No. 1, 2010 pp. 21-27.
  7. K. H. Han, J. H. Kim, "Quantum-inspired evolutionary algorithm for a class of combinatorial optimization," IEEE Trans. Evolut. Comput. ,6(6) (2002) 580–593.
  8. Javidi and Saeed Mehrabi, "On Evolutionary Algorithms for Maximum Independent Set Problem" Journal of Artificial Intelligence: Theory and Application (Vol. 1-2010/Iss. 2), pp. 54-59.
  9. Giandomenico, M, et al. "A New Approach to the Stable Set Problem Based on Ellipsoids," Integer Programming andCombinatorial Optimization, Springer 2011, pp. 223-234.
  10. PM Pardalos, OA Prokopyev, S Busygin "continuous approaches for solving discrete optimization problems. " Handbook on modelling for discrete optimization, 2006 – Springer
  11. http://www. mathworks. com
  12. Grötzsch H. , "Ein Dreifarbensatz für dreikreisfreie Netz auf der Kugel," Z. Martin-Luther-Univ. , 1958.
  13. Herschel A. S. , Sir Wm. , "Hamilton's Icosian Game," Quart. J. Pure Applied Math.
  14. Petersen J. , Die Theorie der regulären Graphen, Acta Math. , 1891.
  15. Ramsey F. P. , On a problem of formal logic, Proc. London Math. Soc. , 1930.
Index Terms

Computer Science
Information Sciences

Keywords

Independent Set Quantum evolutionary algorithm

Powered by PhDFocusTM