Melola Discovery

← Melola Discovery

Akses terbuka Jurnal SINTA 1

A comparative analysis between two heuristic algorithms for the graph vertex coloring problem

International Journal of Electrical and Computer Engineering (IJECE) · Vol. 13 No. 3 (2023)

DOI
10.11591/ijece.v13i3.pp2981-2989
ISSN
2722-2578, 2088-8708
Terbit
2023-06-01
Penerbit
Institute of Advanced Engineering and Science
Lisensi
creativecommons.org/licenses/by-sa/4.0

Abstrak

This study focuses on two heuristic algorithms for the graph vertex coloring problem: the sequential (greedy) coloring algorithm (SCA) and the Welsh–Powell algorithm (WPA). The code of the algorithms is presented and discussed. The methodology and conditions of the experiments are presented. The execution time of the algorithms was calculated as the average of four different starts of the algorithms for all analyzed graphs, taking into consideration the multitasking mode of the operating system. In the graphs with less than 600 vertices, in 90% of cases, both algorithms generated the same solutions. In only 10% of cases, the WPA algorithm generates better solutions. However, in the graphs with more than 1,000 vertices, in 35% of cases, the WPA algorithm generates better solutions. The results show that the difference in the execution time of the algorithms for all graphs is acceptable, but the quality of the solutions generated by the WPA algorithm in more than 20% of cases is better compared to the SC algorithm. The results also show that the quality of the solutions is not related to the number of iterations performed by the algorithms.

Jaringan kolaborasi para penulis

8 penulis · 15 tautan kepenulisan bersama · 2 lintas organisasi

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

  • South-West University "Neofit Rilski"
  • Bulgarian Academy of Sciences
  • 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
Mehrudin SabaniSouth-West University "Neofit Rilski"2
Dafina KostadinovaSouth-West University "Neofit Rilski"2
Petia Koprinkova‐HristovaBulgarian Academy of Sciences2
Viktor AnkovSouth-West University "Neofit Rilski"2
Dimitar ChakalovSouth-West University "Neofit Rilski"2
Toma KatsarskiSouth-West University "Neofit Rilski"2

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>A comparative analysis between two heuristic algorithms for the graph vertex coloring problem</dc:title><dc:creator>Kralev, Velin</dc:creator><dc:creator>Kraleva, Radoslava</dc:creator><dc:description>&lt;jats:p&gt;This study focuses on two heuristic algorithms for the graph vertex coloring problem: the sequential (greedy) coloring algorithm (SCA) and the Welsh–Powell algorithm (WPA). The code of the algorithms is presented and discussed. The methodology and conditions of the experiments are presented. The execution time of the algorithms was calculated as the average of four different starts of the algorithms for all analyzed graphs, taking into consideration the multitasking mode of the operating system. In the graphs with less than 600 vertices, in 90% of cases, both algorithms generated the same solutions. In only 10% of cases, the WPA algorithm generates better solutions. However, in the graphs with more than 1,000 vertices, in 35% of cases, the WPA algorithm generates better solutions. The results show that the difference in the execution time of the algorithms for all graphs is acceptable, but the quality of the solutions generated by the WPA algorithm in more than 20% of cases is better compared to the SC algorithm. The results also show that the quality of the solutions is not related to the number of iterations performed by the algorithms.&lt;/jats:p&gt;</dc:description><dc:publisher>Institute of Advanced Engineering and Science</dc:publisher><dc:date>2023-06-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.v13i3.pp2981-2989</dc:identifier><dc:identifier>10.11591/ijece.v13i3.pp2981-2989</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 13 No 3 (2023); 2981</dc:source><dc:source>2722-2578</dc:source><dc:source>2088-8708</dc:source><dc:relation>https://ijece.iaescore.com/index.php/IJECE/article/viewFile/28561/16545</dc:relation><dc:rights>http://creativecommons.org/licenses/by-sa/4.0</dc:rights></oai_dc:dc>