Knapsack in graph groups

DOI10.1007/S00224-017-9808-3MaRDI QIDQ1702854zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Georg Zetzsche

Publication date 1 March 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-017-9808-3

zbMATH Keywords

combinatorial group theorydecision problems in group theorygraph groupsknapsack problems

Mathematics Subject Classification ID

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) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• Knapsack in graph groups, HNN-extensions and amalgamated products
• The Complexity of Knapsack in Graph Groups
• Knapsack in hyperbolic groups
• Knapsack in hyperbolic groups
• Knapsack problems in groups

Cites work

• A Bound on Solutions of Linear Integer Equalities and Inequalities
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• A Note on "The Comparability Graph of a Tree"
• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• Algorithmics on SLP-compressed strings: a survey
• Characterizations of the decidability of some problems for regular trace languages
• Combinatorics of Coxeter Groups
• Combinatorics on traces
• Computational Complexity
• Coxeter groups are virtually special
• Efficient Computation in Groups Via Compression
• Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups.
• Evaluating matrix circuits
• Formal Languages and Groups as Memory
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 871949 (Why is no real title available?)
• scientific article; zbMATH DE number 1418329 (Why is no real title available?)
• scientific article; zbMATH DE number 3257446 (Why is no real title available?)
• Isoperimetric functions of groups and computational complexity of the word problem
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack in graph groups, HNN-extensions and amalgamated products
• Knapsack problems for NL
• Knapsack problems in groups
• Knapsack problems in products of groups
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Logspace computations in graph products
• Membership problems for regular and context-free trace languages
• Minimal solutions of linear diophantine systems : bounds and algorithms
• Morse theory and finiteness properties of groups
• On linear and residual properties of graph products
• On the complexity of integer programming
• On the Tape Complexity of Deterministic Context-Free Languages
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Reducibility among combinatorial problems
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
• Subset sum problem in polycyclic groups
• The Complexity of Knapsack in Graph Groups
• The Compressed Word Problem for Groups
• The geometry and topology of reconfiguration
• The Hardest Context-Free Language
• The Smallest Grammar Problem
• The submonoid and rational subset membership problems for graph groups.
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• Unary finite automata vs. arithmetic progressions
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• WORD EQUATIONS OVER GRAPH PRODUCTS

Cited in

(26)

• A relation between the knapsack and group knapsack problems
• The power word problem in graph products
• Closure properties of knapsack semilinear groups
• Knapsack problems for wreath products
• Knapsack in graph groups, HNN-extensions and amalgamated products
• The Complexity of Knapsack in Graph Groups
• scientific article; zbMATH DE number 7139161 (Why is no real title available?)
• Bounded context switching for valence systems
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• Compressed decision problems in hyperbolic groups
• The power word problem
• Knapsack in hyperbolic groups
• Knapsack in hyperbolic groups
• Decidability problem for exponential equations in finitely presented groups
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• The power word problem in graph products
• Exponent equations in HNN-extensions
• Compressed decision problems in hyperbolic groups
• The complexity of bidirected reachability in valence systems
• Knapsack problems for NL
• The complexity of knapsack problems in wreath products
• Membership problems in finite groups
• Membership problems in infinite groups
• A characterization of wreath products where knapsack is decidable
• Knapsack problems in products of groups

This page was built for publication: Knapsack in graph groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702854)