{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:28:20Z","timestamp":1747189700849,"version":"3.40.5"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03n04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p> Let [Formula: see text] be a path graph of [Formula: see text] vertices embedded in a metric space. We consider the problem of adding a new edge to [Formula: see text] so that the radius of the resulting graph is minimized, where any center is constrained to be one of the vertices of [Formula: see text]. Previously, the \u201ccontinuous\u201d version of the problem where a center may be a point in the interior of an edge of the graph was studied and a linear-time algorithm was known. Our \u201cdiscrete\u201d version of the problem has not been studied before. We present a linear-time algorithm for the problem. <\/jats:p>","DOI":"10.1142\/s0218195920500089","type":"journal-article","created":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T05:23:32Z","timestamp":1622870612000},"page":"167-182","source":"Crossref","is-referenced-by-count":1,"title":["A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space"],"prefix":"10.1142","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8134-7409","authenticated-orcid":false,"given":"Haitao","family":"Wang","sequence":"first","affiliation":[{"name":"Department of Computer Science, Utah State University, Logan, Utah 84322, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5080-5251","authenticated-orcid":false,"given":"Yiming","family":"Zhao","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Utah State University, Logan, Utah 84322, USA"}]}],"member":"219","published-online":{"date-parts":[[2021,6,4]]},"reference":[{"key":"S0218195920500089BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24766-9_34"},{"key":"S0218195920500089BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_55"},{"key":"S0218195920500089BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.06.004"},{"key":"S0218195920500089BIB004","first-page":"27:1","volume-title":"Proc. 15th Scandinavian Workshop on Algorithm Theory (SWAT)","author":"De Carufel J.-L.","year":"2016"},{"key":"S0218195920500089BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_26"},{"key":"S0218195920500089BIB007","first-page":"40:1","volume-title":"Proc. 29th Int. Symp. Algorithms and Computation (ISAAC)","author":"Bil\u00f2 D.","year":"2018"},{"key":"S0218195920500089BIB008","first-page":"59:1","volume-title":"Proc. 27th Int. Symp. Algorithms and Computation (ISAAC)","author":"Oh E.","year":"2016"},{"key":"S0218195920500089BIB009","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110315"},{"key":"S0218195920500089BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9886-4"},{"key":"S0218195920500089BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.01.016"},{"key":"S0218195920500089BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.014"},{"key":"S0218195920500089BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90007-P"},{"key":"S0218195920500089BIB014","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y"},{"key":"S0218195920500089BIB015","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21719"},{"key":"S0218195920500089BIB016","first-page":"9:1","volume-title":"Proc. 28th Int. Symp. Algorithms and Computation (ISAAC)","author":"Bae S.","year":"2017"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195920500089","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T10:34:58Z","timestamp":1629196498000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195920500089"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":15,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1142\/S0218195920500089"],"URL":"https:\/\/doi.org\/10.1142\/s0218195920500089","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}