document: The quadratic 0-1 knapsack problem with series-parallel support We consider various special cases of the quadratic 0-1 knapsack problem -LRB- QKP -RRB- for which the underlying graph structure is fairly simple . For the variant with edge series-parallel graphs , we give a dynamic programming algorithm with pseudo-polynomial time complexity , and a fully polynomial time approximation scheme . In strong contrast to this , the variant with vertex series-parallel graphs is shown to be strongly NP-complete
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O B I I O O O O O O O B I I I I O O O O O O O O O O O O O O O O O O O
extractive_keyphrases: underlying graph structure dynamic programming algorithm fully polynomial time approximation scheme
abstractive_keyphrases: quadratic 0-1 knapsack problem series-parallel support pseudo-polynomial time complexity np-complete problem