Maximal independent sets in grid graphs

DOI10.1111/ITOR.12291MaRDI QIDQ2968510zbMATH OpenOpenAlexFDO

Authors 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

enumerationgrid graphindependent graphmaximal independent set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Maximal independent sets on a grid graph
• Counting maximal distance-independent sets in grid graphs
• The Number of Independent Sets in a Grid Graph
• Maximal k-independent sets in graphs
• Maximal independent sets in clique-free graphs
• Maximal independent sets and regularity of graphs
• On the number of maximal independent sets in a graph
• The number of maximum independent sets in graphs
• Maximal independent sets in bipartite graphs
• On the number of maximum independent sets of graphs

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Binomial-combinatorial properties of Clar structures
• Counting maximal distance-independent sets in grid graphs
• Counting Maximal Independent Sets in Subcubic Graphs
• Counting non-isomorphic maximal independent sets of the n-cycle graph
• Counting the number of independent sets in chordal graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Generate all maximal independent sets in permutation graphs
• scientific article; zbMATH DE number 2186905 (Why is no real title available?)
• Maximal independent sets in caterpillar graphs
• On cliques in graphs
• Parallel resource co-allocation for the computational grid
• The complexity of computing the permanent
• The number of maximal independent sets in a connected graph
• The number of maximal independent sets in connected graphs
• The number of maximal independent sets in connected triangle-free graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs

Cited in

(6)

• Maximal independent sets on a grid graph
• Every grid has an independent \([1, 2]\)-set
• Counting maximal distance-independent sets in grid graphs
• On generating functions and limit theorems associated with maximal independent sets in grid graphs
• Enumerating independent vertex sets in grid graphs
• On covering an independent set in a grid with a second independent set

This page was built for publication: Maximal independent sets in grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968510)