Article citationsMore>>

Huang, Z.Y., England, M., Davenport, J.H. and Paulson, L.C. (2016) Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition with Groebner Bases. 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), Timisoara, 24-27 September 2016, 45-52.
https://doi.org/10.1109/SYNASC.2016.020

has been cited by the following article:

• TITLE: Solving the k-Independent Sets Problem of Graphs by Gröbner Bases

  AUTHORS: Junyu Luo, Shengzhen Ding

  KEYWORDS: k-Independent Set, Maximal Independent Set, Gröbner Bases

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.13 No.3, July 6, 2023

  ABSTRACT: The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for. 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, the numerical example is presented to illustrate the effectiveness of this algebraic computational method.