Photo from wikipedia
The problem of counting the number of independent sets of a graph G (denoted as i(G)) is a classic #P-complete problem. We present some patterns on graphs that allows us… Click to show full abstract
The problem of counting the number of independent sets of a graph G (denoted as i(G)) is a classic #P-complete problem. We present some patterns on graphs that allows us the polynomial computation of i(G). For example, we show that for a graph G where its set of cycles can be arranged as embedded cycles, i(G) can be computed in polynomial time. Particularly, our proposal counts independent sets on outerplanar graphs.
Keywords:
graphs;
computation;
pattern;
number independent;
independent sets
Journal Title: Pattern Recognition
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Pattern Recognition
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!