A Novel Method for Counting Independent Sets in a Grid Graph
Keywords:Counting independent sets, Grid graph, Transfer matrix, Fibonacci recurrence
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.
How to Cite
Copyright (c) 2023 International Journal of Combinatorial Optimization Problems and Informatics
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.