The Complexity of Knapsack in Graph Groups

DOI10.4230/LIPIcs.STACS.2017.52zbMath1402.68103arXiv1610.00373MaRDI QIDQ4636653

Markus Lohrey, Georg Zetzsche

Publication date: 19 April 2018

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

zbMATH Keywords

knapsacksubset sumgraph groupsdecision problems in group theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Knapsack in graph groups ⋮ Closure properties of knapsack semilinear groups ⋮ Knapsack Problems for Wreath Products

This page was built for publication: The Complexity of Knapsack in Graph Groups