Counting and enumerating independent sets with applications to combinatorial optimization problems

Frank Gurski () and Carolin Rehs ()
Additional contact information
Frank Gurski: University of Düsseldorf
Carolin Rehs: University of Düsseldorf

Mathematical Methods of Operations Research, 2020, vol. 91, issue 3, No 3, 439-463

Abstract: 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 instances of those problems correspond to independent sets in threshold graphs and k-threshold graphs, we obtain polynomial time results for special knapsack and multidimensional knapsack instances. Also, we show lower and upper bounds for the number of necessary bins in several bin packing problems.

Keywords: Knapsack problem; Multidimensional knapsack problem; Threshold graphs; Independent sets; 05C85; 05A15; 05C69 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-019-00696-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:91:y:2020:i:3:d:10.1007_s00186-019-00696-4

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-019-00696-4

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().