Melola Discovery

← Melola Discovery

Akses terbuka Jurnal SINTA 1

An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs

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

DOI
10.11591/ijece.v15i4.pp3867-3875
ISSN
2722-2578, 2088-8708
Terbit
2025-08-01
Penerbit
Institute of Advanced Engineering and Science
Lisensi
creativecommons.org/licenses/by-sa/4.0

Abstrak

In this research an analysis between the Welsh-Powell and DSatur algorithms for the graph vertex coloring problem was presented. Both algorithms were implemented and analyzed as well. The method of the experiment was discussed and the 46 test graphs, which were divided into two sets, were presented. The results show that for sparse graphs with a smaller number of vertices and edges, both algorithms can be used for solving the problem. The results show that in 50% of the cases the Welsh-Powell algorithm found better solutions (23 in total). So, the DSatur algorithm found better solutions in only 19.6% of cases (9 in total). In the remaining 30.4% of cases, both algorithms found identical solutions. For graphs with a larger number of vertices, the usage of the Welsh-Powell algorithm is recommended as it finds better solutions. The execution time of the DSatur algorithm is greater than the execution time of the Welsh-Powell algorithm, reaching up to a minute for graphs with a larger number of vertices. For graphs with fewer vertices and edges, the execution times of both algorithms are shorter, but the time is still greater for the DSatur algorithm.

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

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>An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs</dc:title><dc:creator>Kraleva, Radoslava</dc:creator><dc:creator>Kralev, Velin</dc:creator><dc:creator>Katsarski, Toma</dc:creator><dc:description>&lt;jats:p&gt;In this research an analysis between the Welsh-Powell and DSatur algorithms for the graph vertex coloring problem was presented. Both algorithms were implemented and analyzed as well. The method of the experiment was discussed and the 46 test graphs, which were divided into two sets, were presented. The results show that for sparse graphs with a smaller number of vertices and edges, both algorithms can be used for solving the problem. The results show that in 50% of the cases the Welsh-Powell algorithm found better solutions (23 in total). So, the DSatur algorithm found better solutions in only 19.6% of cases (9 in total). In the remaining 30.4% of cases, both algorithms found identical solutions. For graphs with a larger number of vertices, the usage of the Welsh-Powell algorithm is recommended as it finds better solutions. The execution time of the DSatur algorithm is greater than the execution time of the Welsh-Powell algorithm, reaching up to a minute for graphs with a larger number of vertices. For graphs with fewer vertices and edges, the execution times of both algorithms are shorter, but the time is still greater for the DSatur algorithm.&lt;/jats:p&gt;</dc:description><dc:publisher>Institute of Advanced Engineering and Science</dc:publisher><dc:date>2025-08-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.v15i4.pp3867-3875</dc:identifier><dc:identifier>10.11591/ijece.v15i4.pp3867-3875</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 15 No 4 (2025); 3867</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/37560/18349</dc:relation><dc:rights>http://creativecommons.org/licenses/by-sa/4.0</dc:rights></oai_dc:dc>