Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width

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, 2019, vol. 89, issue 3, No 4, 432 pages

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). KCG has first been introduced by Yamada et al. and represents incompatibilities between items of the knapsack instance. KFG has been introduced by Pferschy and Schauer and represents the necessity of items for other items. 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 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 graphs and forcing graphs of bounded tree-width of Pferschy and Schauer.

Keywords: Knapsack problem; Forcing graph; Conflict graph; Clique-width; 05C85; 90C39; 05C69 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s00186-019-00664-y 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:89:y:2019:i:3:d:10.1007_s00186-019-00664-y

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

DOI: 10.1007/s00186-019-00664-y

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