Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleSolving the $k$-independent sets problem of graphs by Gr\"obner bases.
Author(s) Xuewei Xiong, Zhonghua Zhao
TypeArticle in Journal
AbstractThe aim of this paper is to given an algebraic computational method for finding maximal inde-
pendent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthen-
ing the problem of finding maximal independent sets of G to the problem of finding k-independent sets in
G for 1 ≤ k ≤ n. It is shown that the existence of k-independent sets in G is equivalent to the existence
of solutions of a system of multivariate polynomial equations. It follows that the problem of finding
k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of
k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved.
Consequently, the maximal independent sets and the independent number of G are obtained after solving
at most n such equations. Finally, a numerical example is presented to illustrated the effectiveness of
this algebraic computational method.
Keywordsk-independent set; maximal independent set; Gröbner bases
ISSN1005-3085
LanguageEnglish
JournalChin. J. Eng. Math.
Volume29
Number5
Pages696--702
PublisherEditorial Board of Chinese Journal of Engineering Mathematics, Faculty of Science, Xi
Year2012
Edition0
Translation No
Refereed No
Webmaster