Melola Discovery

← Melola Discovery

Akses terbuka Jurnal SINTA 1

An analysis between exact and approximate algorithms for the k-center problem in graphs

International Journal of Electrical and Computer Engineering (IJECE) · Vol. 12 No. 2 (2022)

DOI
10.11591/ijece.v12i2.pp2058-2065
ISSN
2722-2578, 2088-8708
Terbit
2022-04-01
Penerbit
Institute of Advanced Engineering and Science
Lisensi
creativecommons.org/licenses/by-sa/4.0

Abstrak

This research focuses on the k-center problem and its applications. Different methods for solving this problem are analyzed. The implementations of an exact algorithm and of an approximate algorithm are presented. The source code and the computation complexity of these algorithms are presented and analyzed. The multitasking mode of the operating system is taken into account considering the execution time of the algorithms. The results show that the approximate algorithm finds solutions that are not worse than two times optimal. In some case these solutions are very close to the optimal solutions, but this is true only for graphs with a smaller number of nodes. As the number of nodes in the graph increases (respectively the number of edges increases), the approximate solutions deviate from the optimal ones, but remain acceptable. These results give reason to conclude that for graphs with a small number of nodes the approximate algorithm finds comparable solutions with those founds by the exact 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
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 exact and approximate algorithms for the k-center problem in graphs</dc:title><dc:creator>Kralev, Velin</dc:creator><dc:creator>Kraleva, Radoslava</dc:creator><dc:creator>Ankov, Viktor</dc:creator><dc:creator>Chakalov, Dimitar</dc:creator><dc:description>&lt;jats:p&gt;&amp;lt;span lang="EN-US"&amp;gt;This research focuses on the k-center problem and its applications. Different methods for solving this problem are analyzed. The implementations of an exact algorithm and of an approximate algorithm are presented. The source code and the computation complexity of these algorithms are presented and analyzed. The multitasking mode of the operating system is taken into account considering the execution time of the algorithms. The results show that the approximate algorithm finds solutions that are not worse than two times optimal. In some case these solutions are very close to the optimal solutions, but this is true only for graphs with a smaller number of nodes. As the number of nodes in the graph increases (respectively the number of edges increases), the approximate solutions deviate from the optimal ones, but remain acceptable. These results give reason to conclude that for graphs with a small number of nodes the approximate algorithm finds comparable solutions with those founds by the exact algorithm.&amp;lt;/span&amp;gt;&lt;/jats:p&gt;</dc:description><dc:publisher>Institute of Advanced Engineering and Science</dc:publisher><dc:date>2022-04-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.v12i2.pp2058-2065</dc:identifier><dc:identifier>10.11591/ijece.v12i2.pp2058-2065</dc:identifier><dc:source>International Journal of Electrical and Computer Engineering (IJECE); Vol 12 No 2 (2022); 2058</dc:source><dc:source>2722-2578</dc:source><dc:source>2088-8708</dc:source><dc:relation>http://ijece.iaescore.com/index.php/IJECE/article/viewFile/25986/15568</dc:relation><dc:rights>http://creativecommons.org/licenses/by-sa/4.0</dc:rights></oai_dc:dc>