Knapsack in graph groups, HNN-extensions and amalgamated products

DOI10.4230/LIPIcs.STACS.2016.50zbMath1380.68229arXiv1509.05957MaRDI QIDQ4601902

Georg Zetzsche, Markus Lohrey

Publication date: 24 January 2018

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

zbMATH Keywords

HNN-extensionsknapsackamalgamated productsgraph groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) 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 (6)

Subset sum problem in polycyclic groups ⋮ Knapsack in graph groups ⋮ Closure properties of knapsack semilinear groups ⋮ Knapsack problem for nilpotent groups ⋮ Knapsack in hyperbolic groups ⋮ Knapsack Problems for Wreath Products

This page was built for publication: Knapsack in graph groups, HNN-extensions and amalgamated products