A Visual Tool for Determining the Maximum Independant Set of a Graph Using the Polynomial Formulation Method

Abstract

Set tak bersandar maksimum merupakan satu masalah prototaip dalam teori graf yang meliputi banyak aplikasi dalam sains dan kejuruteraan. Dalam kertas ini, kami mengkaji masalah menentukan set tak bersandar maksimum bagi graf G (V, E) peringkat n menggunakan kaedah huraian polinomial. Kaedah ini menggunakan jiran nod–nod peringkat pertama dan kedua bagi menentukan sama ada nod–nod tersebut suatu set tak bersandar maksimum. Ia meliputi pengmaksimuman polinomial n pembolehubah, di mana n ialah jumlah nod dalam G. Seterusnya, suatu perisian berbentuk penglihatan bagi menyelesai masalah pencarian set tak bersandar maksimum menggunakan Visual C++ dicadangkan dalam kertas ini. Kata kunci: Set tak bersandar, huraian polinomial, jiran peringkat kedua. Maximum independent set is a prototype problem in a graph theory that has many applications in engineering and science. In this paper, we study the problem of determining the largest number of maximum independent sets of a graph G (V, E) of order n using polynomial formulations. This method uses the first and second order neighbourhoods of nodes to determine whether a node is in the maximum independent set. This involves the maximization of an n–variable polynomial, where n is the number of nodes in G. Finally, we present a visual tool developed using the Visual C++ programming language for solving the maximum independent set problem. Key words: Independent set, polynomial formulation, second-order neighbourhood