The knapsack problem with special neighbor constraints

DOI10.1007/s00186-021-00767-5zbMath1490.90247OpenAlexW4200106371MaRDI QIDQ2123119

Dominique Komander, Frank Gurski, Steffen J. Goebbels

Publication date: 8 April 2022

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00186-021-00767-5

zbMATH Keywords

knapsack problemdirected treesdirected co-graphsminimal series-parallel digraphsneighbor constraints

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items

Cites Work

• Unnamed Item
• Partially ordered knapsack and applications to scheduling
• Complement reducible graphs
• Subset sum problems with digraph constraints
• Directed path-width and directed tree-width of directed co-graphs
• Partial homology relations -- satisfiability in terms of di-cographs
• The knapsack problem with neighbour constraints
• Oriented coloring on recursively defined digraphs
• Approximation of knapsack problems with conflict and forcing graphs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Subset sum problems with special digraph constraints
• Solutions for subset sum problems with special digraph constraints
• How to compute digraph width measures on directed co-graphs
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Computing digraph width measures on directed co-graphs (extended abstract)
• Approximation schemes for a class of subset selection problems
• Fully dynamic recognition algorithm and certificate for directed cographs
• Oriented coloring of msp-digraphs and oriented co-graphs (extended abstract)
• Arc-Disjoint Paths in Decomposable Digraphs
• The 1-Neighbour Knapsack Problem
• Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)
• The Recognition of Series Parallel Digraphs
• Classes of Directed Graphs
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Digraphs

This page was built for publication: The knapsack problem with special neighbor constraints