| Autor: |
De Ita Luna, Guillermo, Vidal, Mireya Tovar, Loranca, Beatríz Bernabé |
| Předmět: |
|
| Zdroj: |
International Journal of Combinatorial Optimization Problems & Informatics; Jan-Apr2023, Vol. 14 Issue 1, p11-18, 8p |
| Abstrakt: |
The problem of counting independent sets of a graph G is not only mathematically relevant and interesting, but also has many applications in physics, mathematics, and theoretical computer science. In this paper, a novel method for counting independent sets on grid-like structures is presented. It starts by explaining the recurrences used by the method to count independent sets on basic topologies of graphs. The method is extended to process grid-like structures of quadratic faces. The proposal has a lower time complexity than the required on the leading and current method based on the transfer matrix for counting independent sets on grids. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
