A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time

Carolin Rehs () and Frank Gurski ()
Additional contact information
Carolin Rehs: Algorithmics for Hard Problems Group
Frank Gurski: Algorithmics for Hard Problems Group

A chapter in Operations Research Proceedings 2017, 2018, pp 295-301 from Springer

Abstract: Abstract We introduce a graph theoretic approach in order to solve a large number of knapsack instances in polynomial time. For this purpose we apply threshold graphs, which have the useful property, that their independent sets correspond to feasible solutions in respective knapsack instances. We present a method to count and enumerate all maximal independent sets in a threshold graph in polynomial time and expanding this method for k-threshold graphs. This allows us to solve special knapsack instances as well as special multidimensional knapsack instances for a fixed number of dimensions in polynomial time. Furthermore, our results improve existing solutions for the maximum independent set problem on k-threshold graphs.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:oprchp:978-3-319-89920-6_40

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_40

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().