{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T22:27:58Z","timestamp":1726439278826},"reference-count":35,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p> If u and v are two conjugate elements of a hyperbolic group then the length of a shortest conjugating element for u and v can be bounded by a linear function of the sum of their lengths, as was proved by Lysenok in [Some algorithmic properties of hyperbolic groups, Izv. Akad. Nauk SSSR Ser. Mat. 53(4) (1989) 814\u2013832, 912]. Bridson and Haefliger showed in [Metrics Spaces of Non-Positive Curvature (Springer-Verlag, Berlin, 1999)] that in a hyperbolic group the conjugacy problem can be solved in polynomial time. We extend these results to relatively hyperbolic groups. In particular, we show that both the conjugacy problem and the conjugacy search problem can be solved in polynomial time in a relatively hyperbolic group, whenever the corresponding problem can be solved in polynomial time in each parabolic subgroup. We also prove that if u and v are two conjugate hyperbolic elements of a relatively hyperbolic group then the length of a shortest conjugating element for u and v is linear in terms of their lengths. <\/jats:p>","DOI":"10.1142\/s0218196715500162","type":"journal-article","created":{"date-parts":[[2015,4,6]],"date-time":"2015-04-06T07:55:08Z","timestamp":1428306908000},"page":"689-723","source":"Crossref","is-referenced-by-count":2,"title":["Time complexity of the conjugacy problem in relatively hyperbolic groups"],"prefix":"10.1142","volume":"25","author":[{"given":"Inna","family":"Bumagin","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Carleton University, Ottawa, ON, Canada K1S 5B6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2015,8,13]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609304004059"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1112\/S0024610706023155"},{"key":"rf3","unstructured":"J. M.\u00a0Alonso, Group Theory from a Geometrical Viewpoint (World Scientific Publisher, River Edge, NJ, 1991)\u00a0pp. 3\u201363."},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S1385-7258(57)50030-9"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196712500166"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12494-9"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196705002529"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.2140\/agt.2004.4.1013"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/372\/06884"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdt037"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.2140\/gt.2003.7.933"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdn018"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.2140\/agt.2013.13.3203"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706002986"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050075"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.5802\/aif.2348"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.2140\/agt.2010.10.1807"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.2140\/gt.2005.9.1501"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.4171\/JNCG\/50"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1997.7184"},{"key":"rf26","first-page":"16","volume":"22","author":"Kharlampovich O.","year":"2012","journal-title":"Internat. J. Algebra Comput."},{"key":"rf27","first-page":"912","volume":"53","author":"Lysenok I. G.","year":"1989","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat."},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1515\/form.2011.089"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-10-04959-7"},{"key":"rf32","first-page":"485","volume":"18","author":"Novikov P. S.","year":"1954","journal-title":"Izv. Akad. Nauk SSSR. Ser. Mat."},{"key":"rf33","series-title":"Trudy Matematicheskogo Institute im. V.A. Steklov","volume-title":"Ob Algoritmi\u010desko\u012d Nerazre\u0161imosti Problemy To\u017edestva Slov v Teorii Grupp","volume":"44","author":"Novikov P. S.","year":"1955"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196791000183"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/360\/06572"},{"key":"rf37","first-page":"vi+100","volume":"179","author":"Osin D. V.","year":"2006","journal-title":"Mem. Amer. Math. Soc."},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(95)00094-1"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/14.1.45"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1007\/s10240-001-8188-y"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1515\/gcc.2011.005"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1515\/crll.2004.007"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196715500162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:10:09Z","timestamp":1565097009000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196715500162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":35,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2015,8,13]]},"published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.1142\/S0218196715500162"],"URL":"https:\/\/doi.org\/10.1142\/s0218196715500162","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}