Algorithmic problems in right-angled Artin groups: complexity and applications
From MaRDI portal
Publication:1628497
DOI10.1016/j.jalgebra.2018.10.023zbMath1499.20090arXiv1802.04870OpenAlexW2962780392WikidataQ128975428 ScholiaQ128975428MaRDI QIDQ1628497
Thomas Koberda, Delaram Kahrobaei, Ramón J. Flores
Publication date: 4 December 2018
Published in: Journal of Algebra (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.04870
Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Geometric group theory (20F65) Cryptography (94A60) Braid groups; Artin groups (20F36) Automorphisms of abstract finite groups (20D45)
Related Items
Geometry and Combinatorics via Right-Angled Artin Groups ⋮ Hamiltonicity via cohomology of right-angled Artin groups ⋮ Algorithmic problems in Engel groups and cryptographic applications ⋮ The relative exponential growth rate of subgroups of acylindrically hyperbolic groups ⋮ An algebraic characterization of 𝑘–colorability
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
- Conjugacy \(p\)-separability of right-angled Artin groups and applications.
- On the subgroups of right-angled Artin groups and mapping class groups
- Subgraph isomorphism in graph classes
- Authentication schemes from actions on graphs, groups, or rings
- Divergence and quasimorphisms of right-angled Artin groups.
- Anti-trees and right-angled Artin subgroups of braid groups
- Edge decompositions into two kinds of graphs
- Graph algebras
- Homology of certain algebras defined by graphs
- Complexity of graph embeddability problems
- NP-completeness of graph decomposition problems
- Forests, frames, and games: Algorithms for matroid sums and applications
- Free Lie algebras and free monoids. Bases of free Lie algebras and factorizations of free monoids
- A practical cryptanalysis of \({\mathrm {walnutdsa}^{\mathrm {TM}}}\)
- Automorphisms of graph groups.
- Embeddability between right-angled Artin groups..
- Special cube complexes
- Combinatorial problems of commutation and rearrangements
- Interpretierbarkeit in der Gruppentheorie
- Efficient solution of some problems in free partially commutative monoids
- An introduction to right-angled Artin groups.
- A Secret Sharing Scheme Based on Group Presentations and the Word Problem
- Shortlex automaticity and geodesic regularity in Artin groups
- Logspace Computations in Graph Groups and Coxeter Groups
- An Obstruction to Embedding Right-Angled Artin Groups in Mapping Class Groups
- How to share a secret
- Embeddability and Universal Theory of Partially Commutative Groups
- Finiteness properties of automorphism groups of right-angled Artin groups
- The conjugacy problem in subgroups of right-angled Artin groups
- Isomorphisms of Graph Groups
- Algorithms for maximum independent sets
- The NP-Completeness of Some Edge-Partition Problems
- The NP-Completeness of Edge-Coloring
- Recognition of subgroups of direct products of hyperbolic groups
- A Generating Set for the Automorphism Group of a Graph Group
- A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry
- Coding and Cryptography
- Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
