ALGORITMA LINEAR - WAKTU UNTUK MASALAH LINTASAN TERPANJANG DALAM GRAF KISI PERSEGI PANJANG

SYAMSUL MAARIF, Drs. Aluysius Sutjijana, M.Sc.

2014 | Skripsi | MATEMATIKA

Permasalahan lintasan terpanjang merupakan masalah NP - hard dan sejauh ini telah diselesaikan secara polinomial untuk sebagian graf. Pada tulisan ini, penulis memberikan algoritma linear - waktu untuk menemukan lintasan terpanjang antara dua titik yang diberikan dalam graf kisi persegi panjang.

The longest path problem is a well-known NP - hard problem and so far it has been solved polynomially only for a few classes of graphs. In this paper, we give a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph.

Kata Kunci : GRAF KISI, LINTASAN TERPANJANG