{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T10:00:17Z","timestamp":1773223217437,"version":"3.50.1"},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p> It is known that the bounded Geodesic Length Problem in free metabelian groups is NP-complete [A. Myasnikov, V. Roman'kov, A. Ushakov and A. Vershik, The word and geodesic problems in free solvable groups, Trans. Amer. Math. Soc.362(9) (2010) 4655\u20134682] (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 \u2124<jats:sup>2<\/jats:sup> 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 \u2124<jats:sup>2<\/jats:sup>. <\/jats:p>","DOI":"10.1142\/s0218196711006789","type":"journal-article","created":{"date-parts":[[2011,8,29]],"date-time":"2011-08-29T09:26:06Z","timestamp":1314609966000},"page":"1250012","source":"Crossref","is-referenced-by-count":2,"title":["APPROXIMATION OF GEODESICS IN METABELIAN GROUPS"],"prefix":"10.1142","volume":"22","author":[{"given":"OLGA","family":"KHARLAMPOVICH","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, McGill University, Burnside Hall, Room 1005, 805 Sherbrooke Street West, Montreal, QC, H3A 2K6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ATEFEH","family":"MOHAJERI MOGHADDAM","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, McGill University, Burnside Hall, Room 1005, 805 Sherbrooke Street West, Montreal, QC, H3A 2K6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"rf5","first-page":"223","volume":"2","author":"Elder M.","journal-title":"Groups Complexity Cryptology"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-10-04959-7"},{"key":"rf9","series-title":"Advanced Courses in Mathematics CRM Barcelona","volume-title":"Group-Based Cryptography","author":"Myasnikov A.","year":"2008"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1992-1062874-3"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196711006789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:40:47Z","timestamp":1565181647000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196711006789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":5,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1142\/S0218196711006789"],"URL":"https:\/\/doi.org\/10.1142\/s0218196711006789","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}