Linear Pseudo-Polynomial Factor Algorithm for Automaton Constrained Tree Knapsack Problem

Soh Kumabe, Takanori Maehara, Ryoma Sin'ya

The automaton constrained tree knapsack problem is a variant of the knapsack problem in which the items are associated with the vertices of the tree, and we can select a subset of…