Melola Discovery

← Melola Discovery

Akses terbuka Jurnal SINTA 1

An analysis between different 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.pp2972-2980
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 research focuses on an analysis of different algorithms for the graph vertex coloring problem. Some approaches to solving the problem are discussed. Moreover, some studies for the problem and several methods for its solution are analyzed as well. An exact algorithm (using the backtracking method) is presented. The complexity analysis of the algorithm is discussed. Determining the average execution time of the exact algorithm is consistent with the multitasking mode of the operating system. This algorithm generates optimal solutions for all studied graphs. In addition, two heuristic algorithms for solving the graph vertex coloring problem are used as well. The results show that the exact algorithm can be used to solve the graph vertex coloring problem for small graphs with 30-35 vertices. For half of the graphs, all three algorithms have found the optimal solutions. The suboptimal solutions generated by the approximate algorithms are identical in terms of the number of colors needed to color the corresponding graphs. The results show that the linear increase in the number of vertices and edges of the analyzed graphs causes a linear increase in the number of colors needed to color these graphs.

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>An analysis between different 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;&amp;lt;span lang="EN-US"&amp;gt;This research focuses on an analysis of different algorithms for the graph vertex coloring problem. Some approaches to solving the problem are discussed. Moreover, some studies for the problem and several methods for its solution are analyzed as well. An exact algorithm (using the backtracking method) is presented. The complexity analysis of the algorithm is discussed. Determining the average execution time of the exact algorithm is consistent with the multitasking mode of the operating system. This algorithm generates optimal solutions for all studied graphs. In addition, two heuristic algorithms for solving the graph vertex coloring problem are used as well. The results show that the exact algorithm can be used to solve the graph vertex coloring problem for small graphs with 30-35 vertices. For half of the graphs, all three algorithms have found the optimal solutions. The suboptimal solutions generated by the approximate algorithms are identical in terms of the number of colors needed to color the corresponding graphs. The results show that the linear increase in the number of vertices and edges of the analyzed graphs causes a linear increase in the number of colors needed to color these graphs.&amp;lt;/span&amp;gt;&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.pp2972-2980</dc:identifier><dc:identifier>10.11591/ijece.v13i3.pp2972-2980</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 13 No 3 (2023); 2972</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/28413/16544</dc:relation><dc:rights>http://creativecommons.org/licenses/by-sa/4.0</dc:rights></oai_dc:dc>