On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees (Q4744041)
From MaRDI portal
scientific article; zbMATH DE number 3799379
Language | Label | Description | Also known as |
---|---|---|---|
English | On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees |
scientific article; zbMATH DE number 3799379 |
Statements
On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees (English)
0 references
1983
0 references
acyclic directed graph
0 references
partially ordered knapsack problem
0 references
maximum- valued subset of vertices
0 references
out-tree
0 references
dynamic programming techniques
0 references
pseudopolynomial time optimization algorithms
0 references
fully polynomial time approximation schemes
0 references
complexity results
0 references
weighted and valued graph
0 references
NP- completeness
0 references