Melola Discovery

← Melola Discovery

Akses terbuka Jurnal SINTA 1

Influence of the graph density on approximate algorithms for the graph vertex coloring problem

International Journal of Electrical and Computer Engineering (IJECE) · Vol. 15 No. 5 (2025)

DOI
10.11591/ijece.v15i5.pp4714-4722
ISSN
2722-2578, 2088-8708
Terbit
2025-10-01
Penerbit
Institute of Advanced Engineering and Science
Lisensi
creativecommons.org/licenses/by-sa/4.0

Abstrak

This research explores two heuristic algorithms designed to efficiently solve the graph coloring problem. The implementation codes for both algorithms are provided for better understanding and practical application. The experimental methodology is thoroughly discussed to ensure clarity and reproducibility. The execution times of the algorithms were measured by running the test applications six times for each analyzed graph. The results indicate that the first algorithm generally produced better solutions than the second. In only two instances did the first algorithm produce solutions comparable to those of the second. The results reveal another trend: as the graph density exceeds 85%, the number of required colors increases significantly for both algorithms. However, even at a density of 95%, the number of colors required to color the graph's vertices does not exceed half the total number of vertices. As the graph density increases from 95% to 100%, the number of colors required to color the graph rises significantly. However, when the graph density exceeds 97%, both algorithms produce identical solutions.

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 22 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>Influence of the graph density on approximate 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 research explores two heuristic algorithms designed to efficiently solve the graph coloring problem. The implementation codes for both algorithms are provided for better understanding and practical application. The experimental methodology is thoroughly discussed to ensure clarity and reproducibility. The execution times of the algorithms were measured by running the test applications six times for each analyzed graph. The results indicate that the first algorithm generally produced better solutions than the second. In only two instances did the first algorithm produce solutions comparable to those of the second. The results reveal another trend: as the graph density exceeds 85%, the number of required colors increases significantly for both algorithms. However, even at a density of 95%, the number of colors required to color the graph's vertices does not exceed half the total number of vertices. As the graph density increases from 95% to 100%, the number of colors required to color the graph rises significantly. However, when the graph density exceeds 97%, both algorithms produce identical solutions.&lt;/jats:p&gt;</dc:description><dc:publisher>Institute of Advanced Engineering and Science</dc:publisher><dc:date>2025-10-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.v15i5.pp4714-4722</dc:identifier><dc:identifier>10.11591/ijece.v15i5.pp4714-4722</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 15 No 5 (2025); 4714</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/37499/18440</dc:relation><dc:rights>http://creativecommons.org/licenses/by-sa/4.0</dc:rights></oai_dc:dc>