APLIKASI TEORI DOMINATING SET DALAM PENENTUAN LOKASI PELAYANAN PEMBUATAN KTP DI KABUPATEN JEMBER

Abstract

Penentuan lokasi layanan pembuatan KTP di Kabupaten Jember memerlukan pendekatan yang efisien untuk menjangkau seluruh kecamatan dengan sumber daya terbatas. Penelitian ini menerapkan teori graf khususnya konsep dominating set untuk merepresentasikan peta administratif Kabupaten Jember dalam bentuk graf tak berbobot, dimana setiap kecamatan diwakili titik dan hubungan keterhubungan titik diwakili sisi jika dua kecamatan berbatasan langsung. Graf yang dihasilkan memiliki 31 simpul dan derajat maksimum 7. Berdasarkan Lemma 1, diperoleh batas teoretis ⌈319⌉≤𝛾(𝐺)≤24. Dengan algoritma konstruksi dominating set, penelitian ini berhasil menentukan bahwa dominating number graf tersebut adalah delapan titik. Hasil ini tidak hanya valid secara matematis, tetapi juga menunjukkan efisiensi alokasi stok blangko, personel, dan infrastruktur pelayanan publik. Rekomendasi lokasi berdasarkan dominating set ini dapat dijadikan acuan perencanaan administratif oleh pemerintah daerah serta diadaptasi untuk layanan publik lain yang menuntut cakupan wilayah luas dengan biaya yang lebih efisien.