Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00186 The Knapsack Problem with Conflict Graphs Ulrich Pferschy and Joachim Schauer Vol. 13, no. 2, pp. 233-249, 2009. Regular paper Abstract We extend the classical 0-1 knapsack problem by introducing disjunctive constraints for pairs of items which are not allowed to be packed together into the knapsack. These constraints are represented by edges of a conflict graph whose vertices correspond to the items of the knapsack problem. Similar conditions were treated in the literature for bin packing and scheduling problems. For the knapsack problem with conflict graphs, exact and heuristic algorithms were proposed in the past. While the problem is strongly NP-hard in general, we present pseudopolynomial algorithms for two special graph classes, namely graphs of bounded treewidth (including trees and series-parallel graphs) and chordal graphs. From these algorithms we can easily derive fully polynomial time approximation schemes (FPTAS).
|
Revised: July 2009. Submitted: October 2008. Final: August 2009. Published: October 2009. Reviewed: May 2009. Communicated by Dorothea Wagner |
| Journal of Graph Algorithms and Applications |