Counting and enumerating independent sets with applications to combinatorial optimization problems

Volume: 91, Issue: 3, Pages: 439 - 463
Published: Dec 17, 2019
Abstract
Counting and enumerating maximal and maximum independent sets are well-studied problems in graph theory. In this paper we introduce methods to count and enumerate maximal/maximum independent sets in threshold graphs and k-threshold graphs and improve former results for these problems. The results can be applied to combinatorial optimization problems, and in particular to different variations of the knapsack problem. As feasible solutions for...
Paper Details
Title
Counting and enumerating independent sets with applications to combinatorial optimization problems
Published Date
Dec 17, 2019
Volume
91
Issue
3
Pages
439 - 463
Citation AnalysisPro
  • Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
  • Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.