Approximation of Geodesics in Metabelian Groups

Details Approximation of Geodesics in Metabelian Groups Approximation of Geodesics in Metabelian Groups

2011-06-20

arxiv.org/abs/1106.4035v2

Mathematics

Group Theory

10 pages, 1 figure; International Journal of Algebra and Computation (IJAC), 2011

Scientific paper

10.1142/S0218196711006789

It is known that the bounded Geodesic Length Problem in free metabelian groups is NP-complete (in particular, the Geodesic Problem is NP-hard). We construct a 2-approximation polynomial time deterministic algorithm for the Geodesic Problem. We show that the Geodesic Problem in the restricted wreath product of a finitely generated non-trivial group with a finitely generated abelian group containing $Z^2$ is NP-hard and there exists a Polynomial Time Approximation Scheme for this problem. We also show that the Geodesic Problem in the restricted wreath product of two finitely generated non-trivial abelian groups is NP-hard if and only if the second abelian group contains $Z^2$.

Affiliated with

Also associated with

No associations

Rating

Approximation of Geodesics in Metabelian Groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation of Geodesics in Metabelian Groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation of Geodesics in Metabelian Groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-177292