wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

maximal_independent_set_counting (406B)

      1 # Maximal independent set counting
      2 
      3 - tractable for [cographs]
      4   - cf [corneil1981complement]
      5   - mentioned in [livshits2021counting]
      6 - [sharpp_hard] even on [chordal_graphs]:
      7   - [okamoto2008counting]
      8 - [approximate_counting]: cf [goldberg2016approximately] on [bipartite_graphs]
      9 
     10 Up: [counting_problem], [maximal_independent_set]
     11 
     12 See also: [maximum_independent_set_counting], [independent_set_counting]