{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:36Z","timestamp":1759638876979},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,2]]},"abstract":"<jats:p> We consider the problem of augmenting an [Formula: see text]-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in [Formula: see text] time, and (ii) the input graph is a tree, running in [Formula: see text] time. We also present an algorithm for paths that computes a [Formula: see text]-approximation in [Formula: see text] time. <\/jats:p>","DOI":"10.1142\/s0129054119500060","type":"journal-article","created":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T03:51:51Z","timestamp":1552449111000},"page":"293-313","source":"Crossref","is-referenced-by-count":3,"title":["Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees"],"prefix":"10.1142","volume":"30","author":[{"given":"Ulrike","family":"Gro\u00dfe","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Angewandte Informatik, Universit\u00e4t Bayreuth, Universit\u00e4tsstrasse 30, 95447 Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Knauer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Angewandte Informatik, Universit\u00e4t Bayreuth, Universit\u00e4tsstrasse 30, 95447 Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Stehn","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Angewandte Informatik, Universit\u00e4t Bayreuth, Universit\u00e4tsstrasse 30, 95447 Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[{"name":"School of Information Technologies, J12, The University of Sydney, NSW 2006, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Canada K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2019,3,12]]},"reference":[{"key":"S0129054119500060BIB001","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y","volume":"35","author":"Alon N.","year":"1999","journal-title":"Journal of Graph Theory"},{"key":"S0129054119500060BIB002","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"Berg M. D.","year":"2008"},{"key":"S0129054119500060BIB003","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2011.05.014","volume":"417","author":"Bil\u00f2 D.","year":"2012","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"S0129054119500060BIB005","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s00453-001-0113-8","volume":"33","author":"Chepoi V.","year":"2002","journal-title":"Algorithmica"},{"key":"S0129054119500060BIB006","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190080408"},{"key":"S0129054119500060BIB007","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990","edition":"1"},{"key":"S0129054119500060BIB008","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/978-3-319-62127-2_26","volume-title":"Algorithms and Data Structures","author":"De Carufel J.-L.","year":"2017"},{"issue":"4","key":"S0129054119500060BIB010","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s004930050035","volume":"18","author":"Erd\u0151s P.","year":"1998","journal-title":"Combinatorica"},{"issue":"1","key":"S0129054119500060BIB011","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/050635675","volume":"38","author":"Farshi M.","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"S0129054119500060BIB012","first-page":"1","author":"Frati F.","year":"2014","journal-title":"Algorithmica"},{"issue":"10","key":"S0129054119500060BIB013","doi-asserted-by":"crossref","first-page":"1626","DOI":"10.1016\/j.dam.2013.01.016","volume":"161","author":"Gao Y.","year":"2013","journal-title":"Discrete Applied Mathematics"},{"key":"S0129054119500060BIB014","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1007\/978-3-662-47672-7_55","volume-title":"Automata, Languages, and Programming","author":"Gro\u00dfe U.","year":"2015"},{"key":"S0129054119500060BIB015","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1002\/jgt.21719","volume":"74","author":"Ishii T.","year":"2013","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"S0129054119500060BIB016","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1007\/s00224-006-1305-z","volume":"41","author":"Kapoor S.","year":"2007","journal-title":"Theory of Computing Systems"},{"issue":"5","key":"S0129054119500060BIB017","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0167-6377(92)90007-P","volume":"11","author":"Li C.-L.","year":"1992","journal-title":"Operations Research Letters"},{"key":"S0129054119500060BIB019","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"Megiddo N.","year":"1979","journal-title":"Math. Oper. Res."},{"key":"S0129054119500060BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"issue":"2","key":"S0129054119500060BIB022","doi-asserted-by":"crossref","first-page":"599","DOI":"10.7155\/jgaa.00275","volume":"16","author":"Rutter I.","year":"2012","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"S0129054119500060BIB023","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1002\/jgt.3190110315","volume":"11","author":"Schoone A. A.","year":"1997","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"S0129054119500060BIB024","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.comgeo.2004.03.006","volume":"28","author":"van Oostrum R.","year":"2004","journal-title":"Computational Geometry"},{"key":"S0129054119500060BIB025","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/978-3-319-62127-2_46","volume-title":"Algorithms and Data Structures","author":"Wang H.","year":"2017"},{"issue":"2","key":"S0129054119500060BIB026","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.comgeo.2009.03.008","volume":"43","author":"Wulff-Nilsen C.","year":"2010","journal-title":"Computational Geometry \u2014 Theory and Applications"},{"key":"S0129054119500060BIB027","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.tcs.2012.03.021","volume":"497","author":"Yang B.","year":"2013","journal-title":"Theoretical Computer Science"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119500060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:40:59Z","timestamp":1565120459000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119500060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2]]},"references-count":23,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2019,3,12]]},"published-print":{"date-parts":[[2019,2]]}},"alternative-id":["10.1142\/S0129054119500060"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119500060","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2]]}}}