Some geodesic problems in groups

Abstract

We consider several algorithmic problems concerning geodesics in finitely generated groups. We show that the three geodesic problems considered by Miasnikov et al [arXiv:0807.1032] are polynomial-time reducible to each other. We study two new geodesic problems which arise in a previous paper of the authors and Fusy [arXiv:0902.0202] .

6 pages

References in corpus (2)

• Counting elements and geodesics in Thompson's group $F$
• On Computing Geodesics in Baumslag-Solitar Groups

Cited by in corpus (5)

• $\mathcal{C}$-graph automatic groups
• Counting elements and geodesics in Thompson's group $F$
• Logspace computations in graph products
• On Computing Geodesics in Baumslag-Solitar Groups
• On minimal crossing number braid diagrams and homogeneous braids