Melola Discovery

← Melola Discovery

Akses terbuka Jurnal SINTA 1

CHN and Swap Heuristic to Solve the Maximum Independent Set Problem

International Journal of Electrical and Computer Engineering (IJECE) · Vol. 7 No. 6 (2017)

DOI
10.11591/ijece.v7i6.pp3583-3592
ISSN
2088-8708, 2088-8708
Terbit
2017-12-01
Penerbit
Institute of Advanced Engineering and Science
Lisensi
creativecommons.org/licenses/by-nc/4.0

Abstrak

We describe a new approach to solve the problem to find the maximum independent set in a given Graph, known also as Max-Stable set problem (MSSP). In this paper, we show how Max-Stable problem can be reformulated into a linear problem under quadratic constraints, and then we resolve the QP result by a hybrid approach based Continuous Hopfeild Neural Network (CHN) and Local Search. In a manner that the solution given by the CHN will be the starting point of the local search. The new approach showed a good performance than the original one which executes a suite of CHN runs, at each execution a new leaner constraint is added into the resolved model. To prove the efficiency of our approach, we present some computational experiments of solving random generated problem and typical MSSP instances of real life problem.

Jaringan kolaborasi para penulis

10 penulis · 15 tautan kepenulisan bersama · 1 lintas organisasi

Arahkan kursor atau ketuk sebuah nama untuk menyorot rekan penulisnya. Klik dua kali untuk membuka halaman penulis.

  • Sidi Mohamed Ben Abdellah University
  • Mohammed V University
  • Afiliasi tidak diketahui
  • Organisasi berbeda
  • Organisasi sama
  • Afiliasi tidak diketahui
  • Garis lebih tebal = lebih banyak artikel bersama · lingkaran lebih besar = lebih banyak artikel
Tampilkan sebagai tabel
Rekan penulisOrganisasiArtikel bersama
Jaouad BoumhidiSidi Mohamed Ben Abdellah University1
Nada FaqirSidi Mohamed Ben Abdellah University1
Youness OubenaallaSidi Mohamed Ben Abdellah University1
Aicha Er-RafygMohammed V University1
Abderrahmane Ez-ZahoutMohammed V University1
Barakat OumkaltoumSidi Mohamed Ben Abdellah University1
Omar El BeqqaliSidi Mohamed Ben Abdellah University1

Afiliasi berasal dari OpenAlex; metadata OAI-PMH jurnal tidak memuatnya. Penulis tanpa ID OpenAlex dicocokkan berdasarkan nama, sehingga dua orang bisa tergabung atau satu orang bisa terpisah.

Data ini berasal dari Crossref (yang disetorkan penerbit), karena endpoint OAI-PMH milik jurnal tidak dapat di-harvest.

Sumber metadata: Crossref API (cadangan, berdasarkan ISSN) https://api.crossref.org/journals/2088-8708/works, pertama di-harvest 27 Okt 2026, terakhir terlihat 15 Nov 2026.
Metadata sebagai oai_dc, dikonversi dari Crossref
<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/"><dc:title>CHN and Swap Heuristic to Solve the Maximum Independent Set Problem</dc:title><dc:creator>Adil, Bouhouch</dc:creator><dc:creator>Chakir, Loqman</dc:creator><dc:creator>Abderrahime, El Qadi</dc:creator><dc:description>&lt;jats:p&gt;&amp;lt;p&amp;gt;We describe a new approach to solve the problem to find the maximum independent set in a given Graph, known also as Max-Stable set problem (MSSP). In this paper, we show how Max-Stable problem can be reformulated into a linear problem under quadratic constraints, and then we resolve the QP result by a hybrid approach based Continuous Hopfeild Neural Network (CHN) and Local Search. In a manner that the solution given by the CHN will be the starting point of the local search. The new approach showed a good performance than the original one which executes a suite of CHN runs, at each execution a new leaner constraint is added into the resolved model. To prove the efficiency of our approach, we present some computational experiments of solving random generated problem and typical MSSP instances of real life problem.&amp;lt;/p&amp;gt;&lt;/jats:p&gt;</dc:description><dc:publisher>Institute of Advanced Engineering and Science</dc:publisher><dc:date>2017-12-01</dc:date><dc:type>info:eu-repo/semantics/article</dc:type><dc:format>application/pdf</dc:format><dc:identifier>https://doi.org/10.11591/ijece.v7i6.pp3583-3592</dc:identifier><dc:identifier>10.11591/ijece.v7i6.pp3583-3592</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 7 No 6 (2017); 3583</dc:source><dc:source>2088-8708</dc:source><dc:source>2088-8708</dc:source><dc:relation>http://ijece.iaescore.com/index.php/IJECE/article/viewFile/8727/7585</dc:relation><dc:rights>http://creativecommons.org/licenses/by-nc/4.0</dc:rights></oai_dc:dc>