Solutions for subset sum problems with special digraph constraints

DOI10.1007/s00186-020-00718-6zbMath1454.90075arXiv2004.04712OpenAlexW3038179692MaRDI QIDQ2216192

Carolin Rehs, Dominique Komander, Frank Gurski

Publication date: 15 December 2020

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

Full work available at URL: https://arxiv.org/abs/2004.04712

zbMATH Keywords

subset sum problemdirected co-graphsseries-parallel digraphsdigraph constraint

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

The knapsack problem with special neighbor constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Directed NLC-width
• A compact labelling scheme for series-parallel graphs
• Complement reducible graphs
• Subset sum problems with digraph constraints
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Directed path-width and directed tree-width of directed co-graphs
• Partial homology relations -- satisfiability in terms of di-cographs
• Directed tree-width
• Upper bounds to the clique width of graphs
• Oriented coloring on recursively defined digraphs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Computing digraph width measures on directed co-graphs (extended abstract)
• Fully dynamic recognition algorithm and certificate for directed cographs
• Arc-Disjoint Paths in Decomposable Digraphs
• Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)
• Powers of tensors and fast matrix multiplication
• Quadratic assignment problems on series-parallel digraphs
• Sequencing with Series-Parallel Precedence Constraints
• The Recognition of Series Parallel Digraphs
• Handbook of Graph Grammars and Computing by Graph Transformation
• A complete axiomatisation for the inclusion of series-parallel partial orders
• Classes of Directed Graphs
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• The Transitive Reduction of a Directed Graph