PENERAPAN ALGORITMA EXACT UNTUK PENCARIAN POHON RENTANG DENGAN DAUN TERBANYAK (MAXIMUM LEAF SPANNING TREE)

PENERAPAN ALGORITMA EXACT UNTUK PENCARIAN POHON RENTANG DENGAN DAUN TERBANYAK (MAXIMUM LEAF SPANNING TREE) Mukhamad Sihabudin 1) dan Purwanto 2) e-mail: [email protected] Universitas Negeri Malang ABSTRAK : Salah satu permasalahan pada pohon rentang adalah pencarian pohon rentang dengan daun terbanyak. Permasalahan tersebut dapat diterapkan untuk penentuan suatu sistem jaringan komputer dengan memaksimalkan user dan meminimumkan server. Metode dalam penentuan pohon rentang dengan daun terbanyak dapat ditentukan dengan menggunakan algoritma exact, yaitu dengan membangun suatu pohon bagian T (subtree) yang memperluas graph G. Proses tersebut dilakukan berulang-ulang dengan menggunakan aturan reduksi dan algoritma exact. Algoritma exact memberikan beberapa pilihan didalam iterasinya. Hal ini memungkinkan terbentuknya pohon rentang daun terbanyak tidak selalu tunggal. Kata kunci : pohon rentang daun maksimal, algoritma exact, aturan reduksi ABSTRACT : One of the spanning tree problem is maximum leaf spanning tree. That problem can be used for computer network system to get maximum user and minimum server. The method to get a maximum leaf of spanning tree using exact algorithm is generate subtree which extends graph G. This process runs repeatly using reduction rule and exact algorithm. Exact algorithm gives some of choses in its iteration. It is posible to get spanning tree with maximum leaf which is not always unique. Keywords : maximum leaf spanning tree, exact algorithm, reduction rule

Di zaman yang modern saat ini, komputer sudah menjadi kebutuhan penting bagi manusia. Kegiatan-kegiatan manusia sekarang ini sudah banyak yang dikerjakan oleh komputer. Salah satu manfaat komputer yaitu internet. Dengan internet manusia akan sangat mudah untuk mencari informasi, berkomunikasi dan kegiatan lain. Teori graph bisa juga diterapkan untuk membantu memaksimalkan kinerja jaringan komputer. Salah satu contohnya adalah permasalahan jaringan adhoc atau juga permasalahan penyiaran. Dalam permasalahan penyiaran / jaringan, ada beberapa titik penyiar (server) dan ada beberapa titik penerima siaran / pengguna (user). Dengan banyaknya pengguna internet pada era modern saat ini, maka dibutuhkan juga banyak server untuk memenuhi kebutuhan pengguna internet. Tentu saja, semakin banyak server akan semakin besar pula pengeluaran bagi perusahaan internet tersebut. Untuk meminimumkan banyaknya titik server, bisa digunakan salah satu konsep pada terapan graph, yaitu daun terbanyak pada pohon rentang (maximum leaf spanning tree). Dengan meminimumkan titik server, maka perusahaan internet akan sedikit mengurangi biaya pengeluarannya. Salah satu penelitian mengenai pohon rentang daun terbanyak untuk suatu graph tidak berarah adalah penelitian dari Fernau (2011) yang menuliskan mengenai permasalahan pohon rentang daun terbanyak dengan menggunakan 1) Mukhamad Sihabudin adalah mahasiswa Jurusan Matematika Universitas Negeri Malang 2) Purwanto adalah dosen Jurusan Matematika Universitas Negeri Malang

algoritma exact. Penelitian tersebut menghitung analisis waktu penyelesaian (running time) dalam permasalahan pohon rentang daun maksimal. Belum ada penjelasan secara detail mengenai langkah-langkah pencarian pohon rentang daun maksimal dengan menggunakan algoritma exact. Oleh karena itu, di dalam tulisan ini akan dijabarkan secara detail mengenai langkah-langkah pencarian pohon rentang daun terbanyak dengan menggunakan algoritma exact. Selain itu juga akan dicari suatu pohon rentang daun terbanyak untuk beberapa graph khusus, yaitu graph roda dan graph lengkap. Suatu graph G  V , E  , dengan V adalah himpunan titik-titik dan E adalah himpunan sisi-sisinya. Pohon rentang (spanning tree) T dari graph G dikatakan mempunyai daun terbanyak jika tidak ada pohon rentang lain yang mempunyai daun lebih banyak. Konsep pencarian pohon rentang daun terbanyak yang digunakan adalah membagi himpunan titiknya menjadi beberapa bagian himpunan. Misalkan G  V , E  , himpunan titik V dibagi menjadi beberapa bagian himpunan, yaitu

V  Free  FL  BN  LN  IN dengan Free adalah titik-titik bebas (free vertices), FL (floating leaves) adalah daun-daun ambang, BN (branching nodes) adalah titik-titik cabang, LN (leaf nodes) adalah titik-titik daun dan IN (internal nodes) adalah titik-titik dalam. Titik-titik dalam (IN / internal nodes) adalah titik-titik yang nantinya tetap menjadi titik dalam. Titik-titik ini tidak mengalami perubahan. Derajat dari titik dalam adalah lebih dari 1. Titik-titik daun (LN / leaf nodes) adalah titik-titik yang mempunyai derajat 1. Titik-titik daun nantinya akan terhubung langsung dengan titik dalam. Titik-titik cabang (BN / branching nodes) adalah titik-titik yang nantinya dapat berubah menjadi titik dalam atau menjadi titik daun. Titik-titik cabang merupakan tetangga dari titik internal. Titik-titik ambang (FL / floating leaves) adalah titik-titik yang nantinya berubah menjadi titik daun. Titik-titik bebas (Free / free vertex) adalah titik-titik pada kondisi awal suatu graph, yang bukan merupakan titik internal dan juga bukan merupakan tetangga dari titik internal. Kunci untuk pencarian pohon rentang daun terbanyak dengan algoritma ini adalah membangun suatu pohon bagian (subtree) T  VT , ET   G dengan

VT  IN  BN  LN . Titik cabang BN (branching nodes) adalah suatu daun pada pohon bagian (subtree) yang terbentuk saat itu, tetapi bisa juga mengalami perubahan menjadi suatu titik internal atau tetap menjadi suatu titik daun akibat dari pengulangan rekursif dari algoritma yang digunakan. Langkah inilah yang akan digunakan untuk pencarian pohon rentang dengan daun terbanyak dari suatu graph G. Definisi 1. Misalkan G  V , E  adalah suatu graph, dan misalkan IN, BN, LN, FL  V adalah himpunan dari titik yang saling bebas dan T  G adalah suatu pohon. Kita katakan T memperluas (extends) (IN, BN, LN, FL) jika dan hanya jika IN  internal T  , LN  leaves T  , BN  internal T   leaves T  dan

FL  internal T    .

Definisi 2. Misalkan G  V , E  adalah suatu graph, misalkan IN, BN, LN, FL  V adalah

x1 , x2 ,..., xl V . Dengan x1  X1 ,..., xl  X l dimana masing-masing X i adalah salah satu dari IN,BL,LN atau FL. Dinotasikan operasi dari perubahan masing-masing xi ke himpunan X i himpunan titik yang saling bebas dan misalkan

secara berturut-turut, dan selain itu, jika X i  IN maka semua y  NFree  xi 

berubah menjadi ke BN dan semua y  N FL  xi  menjadi LN. Notasinya diperluas menjadi Y  X , dimana Y  V . Untuk menyelesaikan suatu hal, algoritma yang akan digunakan menganggap perihal didapatkan dari G,IN, BN, LN, FL dengan memilih suatu himpunan dari operasi pada bentuk x  X . Dituliskan x1,1  X1,1 ,..., x1,l1  X1,l1 ... xk ,1  X k ,1 ,..., xk ,lk  X k ,lk

Untuk menyatakan bahwa algoritma tersebut bercabang menjadi k perihal, dimana pada ke-j, 1  j  k , algoritma menganggap perihal didapatkan dari G,IN,BN,LN,FL denga n menggunakan operasi x j ,1  X j ,1 menjadi x j ,l j  X j ,l j Definisi 3. Aturan Reduksi G  V , E  Misalkan

adalah

suatu

graph,

dan

misalkan

IN  BN  LN  FL  Free adalah partisi dari V . Didefinisikan aturan reduksi

sebagai berikut : (A1) Jika ada dua titik yang terhubung langsung u, v V sedemikian sehingga

u, v  FL atau u, v  BN maka hapus sisi u, v dari G . (A2) Jika ada suatu titik v  BN dengan d  v   0 , maka ubah v menjadi LN. (A3) Jika ada suatu titik bebas v dengan d  v   1 , maka ubah v menjadi FL. (A4) Jika ada suatu titik bebas v dengan tidak ada tetangga pada Free  FL , maka ubah v menjadi FL (A5) Jika ada suatu segitiga  x, y, z di G dengan x suatu titik bebas dan

d  x   2 , maka ubah x menjadi FL (A6) Jika ada suatu titik u  BN dimana memotong titik pada G, maka pilih aturan u  IN (A7) Jika ada dua titik yang terhubung langsung u, v V sedemikian sehingga u  LN dan v V \ IN , maka hapus sisi u, v dari G . HASIL DAN PEMBAHASAN Lemma 1 Misalkan G  V , E  adalah suatu graph dan misalkan IN,BN,LN,FL  V adalah himpunan titik-titik yang saling bebas. Misalkan T adalah suatu pohon dengan daun terbanyak yang diperluas (extends) (IN,BN,LN,FL).

Asumsikan bahwa suatu aturan reduksi, katakan  Ai  , i  1, 2,...,7 diaplikasikan pada hal (IN,BN,LN,FL) dari G . Maka, ada pohon T ' dengan daun terbanyak yang diperluas oleh hal yang diperoleh dari (IN,BN,LN,FL) dengan menerapkan aturan reduksi  Ai  yang mempunyai jumlah daun sama dengan banyak daun dari T. Bukti Anggap bahwa T adalah suatu pohon bagian dari G yang berkorespondensi pada (IN, BN, LN, FL) dan T ' adalah pohon rentang dari G sedemikian sehingga T ' memperluas (IN, BN, LN, FL). Untuk masing-masing aturan dari A1 sampai A7, yaitu  Aturan Reduksi 1 (A1) Misalkan u, v  FL . Maka keduanya merupakan daun dari T ' dan tidak mungkin terhubung langsung pada T ' , jadi hapus sisi u, v dari G. Misalkan

u, v  BN maka keduanya juga tidak boleh terhubung langsung pada T ' , jika tidak maka akan ada suatu lintasan tertutup (cycle) pada T ' yang terdiri dari suatu lintasan dari u ke v pada T (melalui titik internal) dan sisi u, v . Maka dari itu sisi

u, v dapat dihapus dari

G.

 Aturan Reduksi 2 (A2) Misalkan v  BN dan d  v   0 . Maka tidak ada titik bebas (free vertex) yang terhubung langsung dengan v. Karena itu tidak ada titik yang dapat dijadikan suatu cabang dari v dan akibatnya v adalah suatu daun dari T ' . Karena itu, titik v dapat diubah menjadi LN.  Aturan Reduksi 3 (A3) Misalkan v adalah suatu titik bebas (free vertex) dengan d  v   1 . Maka v mempunyai derajat 1 pada T ' dan akibatnya v adalah suatu daun dari T ' . Karena itu titik v dapat diubah menjadi FL.  Aturan Reduksi 4 (A4) Misalkan v suatu titik bebas (free vertex) dengan tidak ada tetangga yang merupakan titik pada Free  FL . Karena itu v hanya terhubung langsung pada satu titik dari BN pada T ' . Akibatnya v adalah suatu daun dari T ' . Karena itu titik v dapat diubah menjadi FL.  Aturan Reduksi 5 (A5) Misalkan  x, y, z adalah suatu segitiga pada G sedemikian sehingga x adalah titik bebas (free vertex) dan d  x   2 . Anggap bahwa x adalah suatu titik internal dari T ' yang memperluas (IN,BN,LN,FL). Karena itu, x terhubung langsung dengan y dan z pada T ' dan akibatnya satu dari mereka adalah induk dari x pada T ' , sebut saja y. Maka, pohon rentang T '' dari G yang diperoleh dari T ' dengan menghapus  x, y dan menambahkan  y, z yang tidak mempunyai daun lebih sedikit dari T ' . Akibatnya, dengan tidak menghilangkan keumuman, x adalah suatu daun pada sebarang pohon rentang dari G yang memperluas (IN,BN,LN,FL) dan mempunyai daun terbanyak yang memungkinkan. Maka dari itu titik x dapat diubah menjadi FL

Aturan ke-5 ini yang sangat dibutuhkan sehingga nantinya T ' merupakan suatu pohon rentang dengan daun terbanyak.  Aturan Reduksi 6 (A6) Misalkan u  BN memotong titik dari G. Maka suatu lintasan tunggal dari akar menuju titik cabang (branching node) u pada pohon T yang melewati satu komponen dari G  u . Karena itu, titik u diharuskan menjadi suatu titik internal dari T ' . Maka dari itu, titik u dapat diubah menjadi IN. Catat bahwa tetanggatetangga dari u yang merupakan titik bebas akan menjadi BN dan tetanggatetangga dari u yang merupakan titik ambang akan menjadi LN.  Aturan Reduksi 7 (A7) Misalkan u, v V adalah titik yang terhubung langsung pada G sedemikian sehingga u  LN dan v V \ IN . Karena u adalah suatu daun dari T dan T ' , u hanya terhubung langsung pada satu titik internal x dari T ' , dimana induknya pada suatu pohon bagian berkorespondensi dengan (IN,BN,LN,FL), yaitu x  IN . Akibatnya , titik tersebut tidak terhubung langsung dengan sebarang v V \ IN pada T ' . Maka dari itu, sisi u, v dapat dihapus dari G. Lemma 2 Algoritma exact dapat digunakan untuk menyelesaikan permasalahan pencarian pohon rentang dengan daun terbanyak untuk suatu graph G  V , E  jika v  3 . Dengan kondisi awal, untuk masing-masing v V dengan IN  v , BN  N  v  dan LN  FL   Bukti Aturan reduksi mengubah suatu partisi P   Free, IN, BN, LN, FL  menjadi suatu partisi P '   Free', IN ', BN ', LN ', FL' , sehingga ada suatu pohon rentang dengan daun terbanyak T ' yang memperluas P ' yang paling sedikit mempunyai daun terbanyak seperti pohon rentang T yang memperluas P. Algoritma Exact Untuk mencari suatu pohon rentang daun terbanyak dari suatu graph G, maka harus dibuat suatu kondisi awal untuk graph G, yaitu dengan membagi himpunan titik-titiknya menjadi beberapa himpunan IN, BN atau Free. Pembagian menjadi himpunan-himpunan tersebut menggunakan Lemma 2, yaitu untuk masing-masing v V dengan IN  v , BN  N  v  dan LN  FL   Berikut langkah-langkah pengulangan rekursif algoritma exact :  Reduksi G sesuai dengan aturan reduksi (A1 sampai A7)  Jika ada beberapa titik v  Free  FL yang tidak dapat dicapai, maka kembalikan hasil 0  Jika V  IN  LN maka kembalikan hasil LN  Pilih suatu titik v  BN dengan derajat terbesar, Jika d  v   3 atau  d  v   2 dan NFL  v     maka

v  LN || v  IN

Jika d  v   2 maka Misalkan himpunan titik  x1 , x2   NFree  v  sedemikian sehingga

d  x1   d  x2  Jika d  x1   2 maka misalkan  z  N  x1  \ v Jika z  Free maka

v  LN || v  IN, x1  IN || v  IN, x1  LN Jika z  FL maka v  IN Jika  N  x1   N  x2   \ FL  v dan

z   NFL  x1   NFL  x2   , d  z   3 maka v  LN || v  IN, x1  IN || v  IN, x1  LN, x2  IN || v  IN, x1  LN, x2  LN,

NFree  x1 , x2   FL, NBN x1 , x2  \ v  LN

Jika tidak v  LN || v  IN, x1  IN || v  IN, x1  LN, x2  IN Jika tidak d  v   1 maka Misalkan P   v  v0 , v1 , v2 ,..., vk  suatu lintasan maksimum sedemikian sehingga d  vi   2, 1  i  k , v1 , v2 ,..., vk  Free Misalkan z  N  vk  \ V  P  Jika z  FL dan d  z   1 maka v0 ,..., vk  IN, z  LN Jika z  FL dan d  z   1 maka v0 ,..., vk 1  IN, vk  LN Jika z  BN maka v  LN Jika z  Free maka v0 ,..., vk  IN, z  IN || v  LN Keterangan : Notasi v  IN || v  LN mengartikan suatu korespondensi cabang-cabang, artinya bisa jadi v merupakan suatu titik internal atau v merupakan suatu titik daun. Hasil 0 artinya tidak dapat ditemukan suatu pohon rentang. Jika terjadi demikian, maka harus dilakukan pemilihan titik v sebagai kondisi awal yang lain. Seperti skema algoritma exact seperti pada Gambar 1 berikut ini :

Gambar 1. Skema Algoritma Exact Jika kondisi awal mempunyai lebih dari satu titik dalam (internal nodes), maka harus dibuat sebarang pohong rentang yang mencakup semua titik dalam yang menjadi kondisi awal. Metode yang digunakan untuk penentuan pohon rentang tersebut adalah metode cutting-down, seperti yang dijelaskan pada bab sebelumnya. Contoh : Misalkan diberikan graph berikut :

Gambar 2. Graph G Akan dicari suatu pohon rentang dengan daun terbanyak dari graph G pada Gambar 2 di atas. Langkah awal untuk mencari suatu pohon rentang dengan daun terbanyak menggunakan algoritma exact yaitu melakukan aturan reduksi. Sebelumnya, sesuai dengan Lemma 2, dibuat kondisi awal, yaitu menentukan titik v sebagai IN dan tetangga dari titik v sebagai BN. Dipilih titik v dengan derajat terbesar, yaitu titik h. Sehingga N  h   g , c, d , e, i adalah BN dan LN  FL   . Diperoleh kondisi awal dengan memilih titik h sebagai titik internal (IN), dan titik g, c, d, e dan i yang merupakan tetangga dari titik h, sebagai titik cabang (BN). Tentu saja, titik selain titik-titik yang telah disebutkan akan menjadi titik bebas (Free). Seperti pada Gambar 3, yaitu gambar graph G1 berikut.

Gambar 3. Graph G1 Setelah diperoleh kondisi awal, langkah selanjutnya adalah mereduksi graph G1 dengan aturan reduksi A1 sampai A7. Langkah ini dilakukan berulang-ulang sampai tidak ada lagi aturan reduksi yang dapat digunakan. Berikut ini adalah hasil reduksi graph G1

Gambar 4. Graph G2 Aturan Reduksi 1 (A1) Untuk u, v  BN maka sisi u, v dihapus dari G1

Gambar 5. Graph G3 Aturan Reduksi 2 (A2) Untuk v  BN dengan d  v   0 maka titik v diubah menjadi LN, sehingga dihasilkan graph G3 Aturan Reduksi 5 (A5) Ada segitiga (lintasan tertutup dengan 3 titik) dengan himpunan titik b, a, f  dan b adalah titik

Gambar 6. Graph G4

bebas dan d  b   2 , sehingga b diubah menjadi FL, sehingga terbentuk graph G4

Setelah tidak ada aturan reduksi yang bisa digunakan, maka digunakan langkah selanjutnya pada algoritma exact. Pilih v  BN dengan derajat yang terbesar. Perhatikan graph G4 pada Gambar 6, himpunan titik-titik g , c, d  BN dan derajat masing-masing

titiknya,

yaitu

deg  g   deg  c   deg  d   1 .

Karena

deg  g   deg  c   deg  d   1 , maka v  g , c, d  . Dipilih titik g sebagai titik v, maka P   g  . Sehingga z  N  g  \ V  P  , yaitu z  f . Karena f  Free maka ada dua pilihan, yaitu  g  IN, dan f  IN  atau  g  LN  . Selanjutnya diambil kondisi yang pertama, yaitu  g  IN, dan f  IN  .

Gambar 7. Graph G5 Diperoleh suatu graph G5 seperti pada Gambar 7 di atas. Karena masih belum tercapai suatu pohon rentang, maka dilanjutkan dengan mengulangi langkah awal algoritma exact. Dengan Definisi 2 diperoleh graph G6 seperti pada Gambar 8 berikut :

Gambar 8. Graph G6 Setelah itu dilanjutkan iterasi kedua algoritma exact. Kembali lagi ke aturan reduksi, selanjutnya reduksi graph G6

Gambar 9. Graph G7 Aturan Reduksi 1 (A1) Untuk u, v  BN maka sisi u, v dihapus dari G6 , sehingga terbentuk graph G7

Gambar 10. Graph G8 Aturan Reduksi 2 (A2) Untuk v  BN dengan d  v   0 maka titik v diubah menjadi LN, sehingga diperoleh graph G8 .

Gambar 11. Graph G9 Aturan Reduksi 7 (A7) Jika ada dua titik yang terhubung langsung u, v V sehingga u  LN dan v V \ IN , maka hapus sisi

u, v dari G8 , diperoleh graph G9

Gambar 12. Graph G10 Aturan Reduksi 2 (A2) Untuk v  BN dengan d  v   0 maka titik v diubah menjadi LN, diperoleh graph G10

Memenuhi Definisi 1. Gambar 13 menunjukkan bahwa T10 memperluas (IN, BN, LN, FL). Karena titik-titik f , g , h  IN  internal T10  dan titik-titik Gambar 13. Pohon T10

b, a, c, d , e, i  LN  leaves T10 

Karena tidak ada lagi aturan reduksi yang dapat digunakan, maka gunakan langkah selanjutnya pada algoritma exact. Diperoleh V  IN  LN , maka kembalikan hasil LN , yaitu LN  6 Diperoleh suatu pohon rentang dengan daun terbanyak, yaitu pohon rentang T V T   V  G  seperti pada Gambar 3.17 dengan dan

E T   b, f  , a, f  ,  f , g , g , h , c, h , d , h , e, h , i, h dengan titik f , g , h  IN dan titik a, b, c, d , e, i  LN , yang mempunyai titik daun sebanyak 6.

Gambar 3.17. Pohon Rentang T

KESIMPULAN DAN SARAN Kesimpulan 1. Untuk menentukan suatu pohon rentang dengan daun terbanyak dari suatu graph G dengan menggunakan algoritma exact, harus dilakukan langkahlangkah berikut : 1. Tentukan suatu graph G 2. Buat kondisi awal, sesuai Lemma 2, yaitu untuk masing-masing v V dengan IN  v , BN  N  v  dan LN  FL   3. Lakukan aturan reduksi (A1 sampai A7) berulang-ulang sampai tidak ada aturan reduksi yang bisa digunakan lagi. 4. Jika V  IN  LN maka kembalikan hasil LN (banyaknya titik daun / leaf nodes) dan berhenti. Jika tidak maka pilih titik v yang merupakan titik cabang yang mempunyai derajat terbesar, dan gunakan langkah algoritma exact, selanjutnya kembali ke langkah 3. 2. Pohon rentang daun terbanyak yang terbentuk tidak selalu tunggal. Ada bentuk lain yang mungkin bisa dibuat karena pada bagian dari algoritma exact ada pemilihan yang dilakukan. Jika memang terdapat lebih dari satu pilihan, tentu saja dimungkinkan akan terbentuk pohon rentang dengan daun terbanyak yang lainnya 3. Menentukan pohon rentang daun terbanyak jika ada beberapa titik dalam (internal nodes) yang ditentukan, harus diperhatikan beberapa kondisi. Jika hanya satu titik dalam yang ditentukan, maka pilih titik dalam tersebut sebagai titik v pada kondisi awal. Jika ada lebih dari satu titik dalam pada kondisi awal, maka terlebih dahulu harus dibuat suatu pohon rentang yang memuat semua titik dalam pada kondisi awal. Selanjutnya algoritma exact dapat digunakan. Saran Tulisan ini masih menyajikan pencarian pohon rentang dengan daun terbanyak dengan kondisi titik awal yang ditentukan dan titik awal yang tidak ditentukan. Permasalahan suatu jaringan terkadang mengharuskan bahwa titik dalam hanya mampu mempunyai titik daun terbatas sebanyak n. Hal ini dapat dijadikan sebagai bahan penelitian, yaitu penentuan pohon rentang daun terbanyak dengan membatasi maksimal daun pada masing-masing titik dalam. DAFTAR RUJUKAN Aldous, J.M dan Wilson, R.J. 1990. Graph and Applications, an Introductory Approach. London: Springer-Verlag. Diestel, Reinhard. 2000. Graph Theory. New York: Springer-Verlag. Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Raible, D., & Rossmanith, P. 2011. An exact algorithm for the Maximum Leaf Spanning Tree problem. Jurnal Komputer dan Sains, TAMU Computer Science Faculty Pages (Online) (http://www.faculty.cs.tamu.edu) diakses 7 April 2012.

Fernau, Henning, dan Raible, Daniel. 2010. An Amortized Search Tree Analysis for k-leaf Spanning Tree. Jurnal Komputer dan Sains, SOFSEM International Conference Devoted To The Theory And Practice Of Computer (Online) (http://www.sofsem.cz) diakses 13 april 2012. Kneis, J., Langer, A., & Rossmanith, P. 2011. A New Algorith for Finding Trees with Many Leaves. Dari Theory Group (Online) (http://www.tcs.rwthaachen.de) diakses 11 agustus 2012 Kratsch, Dieter. 2010. Exact Exponential Algorithms. Dari Laboratoire d’Informatique Theorique et Appliquee Universite Paul Verlaine-Metz (Online) (http://www.dur.ac.uk) diakses 11 agustus 2012. Maculan, N., Lucena, A., & Simonetti, L.G. 2009. Reformulation and Solution Algorithms for the Maximum Leaf Spanning Tree Problem. Dari Springer Science (Online) (http://www.link.springer.com) diakses 7 april 2012 Weisstein, Eric W. Grid Graph. From MathWorld-A Wolfram Web Resource. (http://mathworld.wolfram.com/GridGraph.html) diakses tanggal 30 Juli 2012