Perpustakaan Digital ITB

Steiner tree merupakan suatu topik di dalam Teori Graf yang memiliki penggunaan luas dalam bidang perancangan jaringan yang efisien. Dalam tugas akhir ini dibuat suatu aplikasi yang dapat menyelesaikan masalah pencarian Steiner tree yang diimplementasikan pada pengkonstruksian jaringan pipa gas di Pulau Jawa. Jaringan pipa gas yang dikonstruksi menghubungkan seluruh kota di Pulau Jawa yang memiliki depo gas atau BBM dengan panjang pipa yang minimum. Selain itu, pengkonstruksian jaringan tersebut juga mempertimbangkan faktor topografi (perbedaan ketinggian), mengingat Pulau Jawa memiliki ketinggian yang bervariasi. Algoritma yang digunakan dalam pengkostruksian jaringan ini adalah algoritma heuristic yang dirancang oleh Markowsky et al. Pemilihan algoritma heuristic didasarkan atas kecepatan waktu komputasinya jika dibandingkan dengan algoritma eksak yang bekerja secara brute force untuk memeriksa setiap kemungkinan minimal spanning tree. Bobot Steiner tree yang dihasilkan melalui algoritma heuristic belum tentu merupakan bobot yang minimum, akan tetapi bobot tersebut tidak akan melebihi suatu nilai batas atas.