Maximal independent sets in grid graphs. (20th April 2016)

• Record Type: Journal Article
• Authors: Ortiz, Carmen; Villanueva, Mónica
• Other Names: Cancela Héctor guestEditor.; Martins Simone guestEditor.; Mauttone Antonio guestEditor.; Urquhart María E. guestEditor.
• Is Part Of: International transactions in operational research. Volume 24:Number 1/2(2017)
• Page Start: 369
• Page End: 385
• Publication Date: 2016-04-20
• Subjects: maximal independent set -- enumeration -- grid graph -- independent graph; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12291
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: A grid graph is the Cartesian product of two path graphs. Enumerating all maximal independent sets in a graph is a well‐known combinatorial problem. For a general graph, it is # P − c o m p l e t e . In this work, we provide a polynomial‐time algorithm to generate the whole family of maximal independent sets (mis) of complete grid graphs with two rows. The same algorithm is used in two particular cases: chordless paths and cycles. We apply this result to characterize the independent graph (intersection graph of maximal independent sets) of these three classes of graphs. We also present an alternative proof of Euler's result for grid graphs with three rows that can be used for enumerating the family of mis.