The complexity of some problems on maximal independent sets in graphs

zbMATH Open1162.90580MaRDI QIDQ5301767FDOQ5301767

Authors: Yury L. Orlovich, I.È. Zverovich 

Publication date: 20 January 2009

Recommendations

• Integers for the number of maximal independent sets in graphs
• On graphs with the third largest number of maximal independent sets
• Graphs with the second largest number of maximal independent sets
• The second largest number of maximal independent sets in graphs with at most \(k\) cycles
• scientific article; zbMATH DE number 867639

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Theory of computing (68Q99)

Cited In (15)

• A simple proof that finding a maximal independent set in a graph is in NC
• An optimal maximal independent set algorithm for bounded-independence graphs
• The maximal f-dependent set problem for planar graphs is in NC
• Title not available (Why is that?)
• The Complexity of Finding Paths in Graphs with Bounded Independence Number
• MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS
• Title not available (Why is that?)
• The complexity of dissociation set problems in graphs
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
• On the complexity of the independent set problem in triangle graphs
• Title not available (Why is that?)
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Computing maximum independent set on outerstring graphs and their relatives

This page was built for publication: The complexity of some problems on maximal independent sets in graphs

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