Geodesic
The Knapsack Problem with Conflict Graphs
Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 233-249.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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).
DOI : 10.7155/jgaa.00186
Keywords: knapsack problem, conflict graph 
@article{JGAA_2009_13_2_a9,
     author = {Ulrich Pferschy and Joachim Schauer},
     title = {The {Knapsack} {Problem} with {Conflict} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {233--249},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2009},
     doi = {10.7155/jgaa.00186},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00186/}
}
TY  - JOUR
AU  - Ulrich Pferschy
AU  - Joachim Schauer
TI  - The Knapsack Problem with Conflict Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2009
SP  - 233
EP  - 249
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00186/
DO  - 10.7155/jgaa.00186
LA  - en
ID  - JGAA_2009_13_2_a9
ER  - 
%0 Journal Article
%A Ulrich Pferschy
%A Joachim Schauer
%T The Knapsack Problem with Conflict Graphs
%J Journal of Graph Algorithms and Applications
%D 2009
%P 233-249
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00186/
%R 10.7155/jgaa.00186
%G en
%F JGAA_2009_13_2_a9
Ulrich Pferschy; Joachim Schauer. The Knapsack Problem with Conflict Graphs. Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 233-249. doi : 10.7155/jgaa.00186. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00186/

Cité par Sources :