Simultaneously Computing a Maximal Independent Set Modulo an Ideal and a Gröbner Basis of the Ideal

Ping Liu, Baoxin Shang () and Shugong Zhang
Additional contact information
Ping Liu: School of Mathematics, Key Laboratory of Symbolic Computation and Knowledge Engineering (Ministry of Education), Jilin University, Changchun 130012, China
Baoxin Shang: College of Science, Northeast Electric Power University, Jilin 132012, China
Shugong Zhang: School of Mathematics, Key Laboratory of Symbolic Computation and Knowledge Engineering (Ministry of Education), Jilin University, Changchun 130012, China

Mathematics, 2025, vol. 13, issue 18, 1-14

Abstract: To solve problems on a positive-dimensional ideal, I ⊂ k [ X ] , a maximal independent set U ⊂ X modulo I , and a Gröbner basis of I e , where I e is the extension of I to k ( U ) [ V ] ( V : = X ∖ U ) , are widely used. As far as we know, they are usually computed separately, i.e., U is calculated first and the Gröbner basis is computed after U is obtained. In this paper, we present an efficient algorithm for computing a maximal independent set U modulo I , and a Gröbner basis of I e simultaneously. Differently from computing them separately, the algorithm takes full advantage of the polynomial information throughout the Gröbner basis computation to obtain U as soon as possible; hence, it significantly improves the computing efficiency.

Keywords: maximal independent set; Gröbner basis; positive-dimensional ideal (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/18/3037/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/18/3037/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:18:p:3037-:d:1753922

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().