The Knapsack Problem with Conflict Graphs and Forcing Graphs of Bounded Clique-Width

Frank Gurski () and Carolin Rehs ()
Additional contact information
Frank Gurski: University of Düsseldorf, Institute of Computer Science, Algorithmics for Hard Problems Group
Carolin Rehs: University of Düsseldorf, Institute of Computer Science, Algorithmics for Hard Problems Group

A chapter in Operations Research Proceedings 2018, 2019, pp 259-265 from Springer

Abstract: Abstract The 0-1-knapsack problem is a well-known NP-hard problem in combinatorial optimization. We consider the extensions to the knapsack problem with conflict graph (KCG) and the knapsack problem with forcing graph (KFG). Within this paper we provide pseudo-polynomial solutions for KCG and KFG with co-graphs as conflict and forcing graphs and extend these solutions to conflict and forcing graphs of bounded clique-width. Our solutions are based on dynamic programming using the tree-structure representing the conflict graph and the forcing graph. Further we conclude fully polynomial time approximation schemes (FPTAS) for KCG on conflict graphs of bounded clique-width and KFG on forcing graphs of bounded clique-width. This generalizes the known results for conflict and forcing graphs of bounded tree-width of Pferschy and Schauer.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (4)

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-030-18500-8_33

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

DOI: 10.1007/978-3-030-18500-8_33

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 ().