Solutions for subset sum problems with special digraph constraints
From MaRDI portal
Publication:2216192
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
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
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
