Algorithmic problems in right-angled Artin groups: complexity and applications

Ramón Flores; Delaram Kahrobaei; Thomas Koberda

Algorithmic problems in right-angled Artin groups: complexity and applications

Ramón Flores, Delaram Kahrobaei, Thomas Koberda

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography.

Original language	English
Pages (from-to)	111-129
Journal	Journal of Algebra
Volume	519
Early online date	3 Nov 2018
Publication status	Published - 1 Feb 2019

Bibliographical note

16 pages

Keywords

math.GR
math.AT
math.GT
20F36

Cite this

@article{91a0dc85ce8b4a65923d3cb8f3d2fffe,

title = "Algorithmic problems in right-angled Artin groups: complexity and applications",

abstract = " In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography. ",

keywords = "math.GR, math.AT, math.GT, 20F36",

author = "Ram{\'o}n Flores and Delaram Kahrobaei and Thomas Koberda",

note = "16 pages",

year = "2019",

month = feb,

day = "1",

language = "English",

volume = "519",

pages = "111--129",

journal = "Journal of Algebra",

issn = "0021-8693",

publisher = "Academic Press",

}

TY - JOUR

T1 - Algorithmic problems in right-angled Artin groups

T2 - complexity and applications

AU - Flores, Ramón

AU - Kahrobaei, Delaram

AU - Koberda, Thomas

N1 - 16 pages

PY - 2019/2/1

Y1 - 2019/2/1

N2 - In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography.

AB - In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography.

KW - math.GR

KW - math.AT

KW - math.GT

KW - 20F36

M3 - Article

SN - 0021-8693

VL - 519

SP - 111

EP - 129

JO - Journal of Algebra

JF - Journal of Algebra

ER -