Maximal independent sets in grid graphs

DOI10.1111/itor.12291zbMath1358.90146MaRDI QIDQ2968510

Mónica Villanueva, Carmen Z. Ortiz

Publication date: 16 March 2017

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/itor.12291

zbMATH Keywords

enumeration; grid graph; maximal independent set; independent graph

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Maximal independent sets in caterpillar graphs
• Counting the number of independent sets in chordal graphs
• Binomial-combinatorial properties of Clar structures
• The number of maximal independent sets in a connected graph
• The number of maximal independent sets in connected triangle-free graphs
• Parallel resource co-allocation for the computational grid
• Counting maximal distance-independent sets in grid graphs
• Counting Maximal Independent Sets in Subcubic Graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• The number of maximal independent sets in connected graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Generate all maximal independent sets in permutation graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• On cliques in graphs