A Novel Method for Counting Independent Sets in a Grid Graph

Authors

  • Guillermo De Ita Luna Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación
  • Mireya Tovar Vidal Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación
  • Maria Beatriz Bernábe-Loranca

Keywords:

Counting independent sets, Grid graph, Transfer matrix, Fibonacci recurrence

Abstract

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.

Downloads

Published

2023-02-22

How to Cite

De Ita Luna, G. ., Tovar Vidal, M. ., & Bernábe-Loranca, M. B. (2023). A Novel Method for Counting Independent Sets in a Grid Graph. International Journal of Combinatorial Optimization Problems and Informatics, 14(1), 11–18. Retrieved from https://ijcopi.org/ojs/article/view/334

Issue

Section

Articles

Most read articles by the same author(s)