Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/286815 
Year of Publication: 
2021
Citation: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 95 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2021 [Pages:] 1-34
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
The knapsack problem is one of the simplest and most fundamental NP-hard problems in combinatorial optimization. We consider two knapsack problems which contain additional constraints in the form of directed graphs whose vertex set corresponds to the item set. In the one-neighbor knapsack problem, an item can be chosen only if at least one of its neighbors is chosen. In the all-neighbors knapsack problem, an item can be chosen only if all its neighbors are chosen. For both problems, we consider uniform and general profits and weights. We prove upper bounds for the time complexity of these problems when restricting the graph constraints to special sets of digraphs. We discuss directed co-graphs, minimal series-parallel digraphs, and directed trees.
Subjects: 
Knapsack problem
Neighbor constraints
Directed co-graphs
Minimal series-parallel digraphs
Directed trees
JEL: 
C85
C39
C69
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.