Computer File
Pembangunan geometric spanner menggunakan well-separated pair decomposition
Geometric spanner atau yang disebut juga t-spanner adalah sebuah graf berbobot dari
sebuah himpunan titik dengan bilangan riil t > 1, dimana untuk setiap pasangan titik
di graf terdapat lintasan dengan bobot mendekati nilai t X jarak Euclidean pasangan
titik tersebut.
Pada penelitian ini, algoritma Well-Separated Pair Decomposition akan diimplementasikan
untuk membangun geometric spanner di R2 dengan menggunakan bahasa
pemrograman C++. Algoritma ini bekerja dengan menambahkan sebuah sisi untuk
menghubungkan dua titik dari himpunan well-separated berbeda. Untuk menemukan
semua himpunan titik yang merupakan well-separated di R2, digunakan sebuah struktur
data yang disebut dengan split tree. Selain itu, digunakan beberapa ukuran kualitas
untuk mengukur kualitas dari geometric spanner, yaitu size, weight, dilation, degree,
diameter, connectivity, genus, load factor. Dengan menggunakan himpunan titik yang
sama, akan dibangun juga sebuah minimum spanning tree untuk dibandingkan dengan
geometric spanner dari segi waktu untuk membangun keduanya dan kualitasnya.
Hasil eksperimen menunjukan bahwa waktu yang dibutuhkan untuk membangun
sebuah geometric spanner lebih lama dibanding waktu untuk membangun sebuah minimum
spanning tree. Selanjutnya dari segi kualitas, minimum spanning tree memiliki
kualitas yang lebih baik dibanding geometric spanner dari kualitas size, weight, degree,
dan genus. Akan tetapi, untuk beberapa kualitas seperti dilation, diameter, connectivity,
dan load factor, geometric spanner lebih baik dibanding minimum spanning tree.
Kata-kata kunci: Geometric Spanner, t-Spanner, Jaringan Geometris, Panjang Lintasan, Well-Separated Pair Decomposition, Split Tree, Size, Weight, Dilation, Degree, Diameter, Connectivity, Genus, Load Factor
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
skp28956 | DIG - FTIS | Skripsi | INFO ANG p/14 | Perpustakaan | Tersedia namun tidak untuk dipinjamkan - Missing |
Tidak tersedia versi lain