CD Skripsi

Analisis Perbandingan Algoritma Backtracking, Greedy, Dan Welch-Powell Dalam Menentukan Bilangan Kromatik Pada Graf Modifikasi Adenovirus

---

Adenovirus is a DNA virus that causes infections in the upper or lower respira- tory tract, pharynx, gastrointestinal tract, and conjunctiva. Let G = (AVn) be the modified adenovirus graph, which is constructed from molecular biology da- ta, where V (G) is the set of vertices representing genes of the DNA virus, DNA segments, and their variants, while E(G) is the set of edges representing over- lapping interactions or conflicts between segments. This final project discusses vertex coloring on the modified adenovirus graph (AVn) such that every two adjacent vertices are assigned different colors. The chromatic number is the mi- nimum number of colors used to solve the vertex coloring problem on the graph G and is denoted by χ(G). To determine the chromatic number of the modi- fied adenovirus graph (AVn), three coloring algorithms are applied, specifically the backtracking, greedy, and Welch-Powell algorithms, making this research a collaboration across the fields of mathematics, biology, and computation. The results show that all three algorithms can solve the vertex coloring problem with χ(AVn) = 3 for n = 4, 6, 8, 10, 12 and χ(AVn) = 4 for n = 5, 7, 9, 11. Based on the analysis of these three algorithms, it can be concluded that in terms of execution time, the backtracking algorithm is less efficient for determining the chromatic number of graphs with a larger number of vertices compared to the greedy and Welch-Powell algorithms.
Keywords: Vertex coloring, chromatic number, adenovirus modified graph, backtracking algorithm, greedy algorithm, Welch-Powell algorithm

---

Ketersediaan

Informasi Detail

Judul Seri

-

No. Panggil

2103111082

Penerbit

Pekanbaru : Universitas Riau FMIPA Matematika., 2025

Deskripsi Fisik

-

Bahasa

Indonesia

ISBN/ISSN

-

Klasifikasi

2103111082

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

MATEMATIKA

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Mutia

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar