A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.

zbMath1234.20048arXiv0903.0216MaRDI QIDQ716392

Murray J. Elder

Publication date: 28 April 2011

Published in: Illinois Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

deterministic algorithmsNP-complete problemsmetabelian groupsBaumslag-Solitar groupslinear-time algorithmsgeodesic lengthsgeodesic problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Solvable groups, supersolvable groups (20F16) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

Conjugation curvature in solvable Baumslag–Solitar groups ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Growth in Baumslag–Solitar groups II: The Bass–Serre tree ⋮ Logspace computations in graph products