{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:42Z","timestamp":1740120222439,"version":"3.37.3"},"reference-count":47,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03n04","funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["MTR\/2017\/000474"],"award-info":[{"award-number":["MTR\/2017\/000474"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>Given a set [Formula: see text] of [Formula: see text] points, a weight function [Formula: see text] to associate a non-negative weight to each point in [Formula: see text], a positive integer [Formula: see text], and a real number [Formula: see text], we present algorithms for computing a spanner network [Formula: see text] for the metric space [Formula: see text] induced by the weighted points in [Formula: see text]. The weighted distance function [Formula: see text] on the set [Formula: see text] of points is defined as follows: for any [Formula: see text], [Formula: see text] is equal to [Formula: see text] if [Formula: see text], otherwise, [Formula: see text] is [Formula: see text]. Here, [Formula: see text] is the Euclidean distance between [Formula: see text] and [Formula: see text] if points in [Formula: see text] are in [Formula: see text], otherwise, it is the geodesic (Euclidean) distance between [Formula: see text] and [Formula: see text]. The following are our results: (1) When the weighted points in [Formula: see text] are located in [Formula: see text], we compute a [Formula: see text]-vertex fault-tolerant [Formula: see text]-spanner network of size [Formula: see text]. (2) When the weighted points in [Formula: see text] are located in the relative interior of the free space of a polygonal domain [Formula: see text], we detail an algorithm to compute a [Formula: see text]-vertex fault-tolerant [Formula: see text]-spanner network with [Formula: see text] edges. Here, [Formula: see text] is the number of simple polygonal holes in [Formula: see text]. (3) When the weighted points in [Formula: see text] are located on a polyhedral terrain [Formula: see text], we propose an algorithm to compute a [Formula: see text]-vertex fault-tolerant [Formula: see text]-spanner network, and the number of edges in this network is [Formula: see text].<\/jats:p>","DOI":"10.1142\/s021819592250008x","type":"journal-article","created":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T14:47:55Z","timestamp":1670856475000},"page":"175-199","source":"Crossref","is-referenced-by-count":0,"title":["Vertex Fault-Tolerant Geometric Spanners for Weighted Points"],"prefix":"10.1142","volume":"32","author":[{"given":"Sukanya","family":"Bhattacharjee","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Guwahati, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7141-0977","authenticated-orcid":false,"given":"R.","family":"Inkulu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Guwahati, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,12,12]]},"reference":[{"issue":"2","key":"S021819592250008XBIB001","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/s00453-016-0268-y","volume":"80","author":"Abam M. A.","year":"2018","journal-title":"Algorithmica"},{"issue":"4","key":"S021819592250008XBIB002","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1007\/s00454-011-9343-y","volume":"45","author":"Abam M. A.","year":"2011","journal-title":"Discr. Comput. Geom."},{"key":"S021819592250008XBIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9137-7"},{"issue":"1","key":"S021819592250008XBIB004","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00453-010-9465-2","volume":"61","author":"Abam M. A.","year":"2011","journal-title":"Algorithmica"},{"key":"S021819592250008XBIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.01.008"},{"issue":"6","key":"S021819592250008XBIB006","doi-asserted-by":"crossref","first-page":"1796","DOI":"10.1137\/18M119358X","volume":"48","author":"Abam M. A.","year":"2019","journal-title":"SIAM J. Comput."},{"key":"S021819592250008XBIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-011-0346-7"},{"issue":"2","key":"S021819592250008XBIB008","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1137\/S0895480191198768","volume":"7","author":"Alon N.","year":"1994","journal-title":"SIAM J. Discr. Math."},{"key":"S021819592250008XBIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"S021819592250008XBIB010","first-page":"514","volume-title":"Proceedings of European Symposium on Algorithms","author":"Arikati S. R.","year":"1996"},{"key":"S021819592250008XBIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.07.004"},{"key":"S021819592250008XBIB012","first-page":"489","volume-title":"Proceedings of Annual ACM Symposium on Theory of Computing","author":"Arya S.","year":"1995"},{"issue":"2","key":"S021819592250008XBIB013","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0925-7721(99)00014-0","volume":"13","author":"Arya S.","year":"1999","journal-title":"Comput. Geom."},{"key":"S021819592250008XBIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523237"},{"key":"S021819592250008XBIB015","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/978-3-030-11509-8_3","volume-title":"Proceedings of Conference on Algorithms and Discrete Applied Mathematics","author":"Bhattacharjee S.","year":"2019"},{"issue":"3","key":"S021819592250008XBIB016","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jda.2012.03.004","volume":"15","author":"Bose P.","year":"2012","journal-title":"J. Discr. Algorithms"},{"issue":"2","key":"S021819592250008XBIB017","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.comgeo.2012.07.001","volume":"46","author":"Bose P.","year":"2013","journal-title":"Comput. Geom."},{"issue":"2","key":"S021819592250008XBIB018","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.comgeo.2008.04.003","volume":"42","author":"Bose P.","year":"2009","journal-title":"Comput. Geom."},{"key":"S021819592250008XBIB019","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9293-4"},{"issue":"3","key":"S021819592250008XBIB020","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/j.jda.2011.03.001","volume":"9","author":"Bose P.","year":"2011","journal-title":"J. Discr. Algorithms"},{"key":"S021819592250008XBIB021","first-page":"81","volume-title":"Japanese Conference on Discrete and Computational Geometry","author":"Bose P.","year":"1998"},{"key":"S021819592250008XBIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0476-8"},{"issue":"3","key":"S021819592250008XBIB023","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00453-005-1168-8","volume":"42","author":"Bose P.","year":"2005","journal-title":"Algorithmica"},{"key":"S021819592250008XBIB024","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195909002861"},{"issue":"1","key":"S021819592250008XBIB025","first-page":"196","volume":"3","author":"Carmi P.","year":"2012","journal-title":"J. Comput. Geom."},{"key":"S021819592250008XBIB026","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9115-5"},{"issue":"4","key":"S021819592250008XBIB027","volume":"12","author":"Chan T.-H. H.","year":"2016","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"S021819592250008XBIB028","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1137\/130930984","volume":"44","author":"Chan T.-H. H.","year":"2015","journal-title":"SIAM J. Comput."},{"key":"S021819592250008XBIB029","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"issue":"2","key":"S021819592250008XBIB030","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00454-004-1121-7","volume":"32","author":"Czumaj A.","year":"2004","journal-title":"Discr. Comput. Geom."},{"key":"S021819592250008XBIB031","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","volume-title":"Optimal Algorithms","author":"Das G.","year":"1989"},{"issue":"4","key":"S021819592250008XBIB032","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1142\/S0218195997000193","volume":"7","author":"Das G.","year":"1997","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"S021819592250008XBIB033","first-page":"425","author":"Eppstein D.","year":"1999","journal-title":"Handbook of Computational Geometry"},{"key":"S021819592250008XBIB034","first-page":"478","volume-title":"Proc. European Symposium on Algorithms","author":"Gottlieb L.-A.","year":"2008"},{"key":"S021819592250008XBIB035","first-page":"53","volume-title":"Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2: Contemporary and Emerging Applications","author":"Gudmundsson J.","year":"2018"},{"key":"S021819592250008XBIB036","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"S021819592250008XBIB037","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"S021819592250008XBIB038","first-page":"135","author":"Le H.","year":"2022","journal-title":"SIAM J. Comput."},{"issue":"1","key":"S021819592250008XBIB039","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"Levcopoulos C.","year":"2002","journal-title":"Algorithmica"},{"key":"S021819592250008XBIB040","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"S021819592250008XBIB041","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/3-540-48447-7_20","volume-title":"Proc. Workshop on Algorithms and Data Structures","author":"Lukovszki T.","year":"1999"},{"key":"S021819592250008XBIB042","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"issue":"1","key":"S021819592250008XBIB043","first-page":"1989","volume":"13","author":"Peleg D.","journal-title":"J. Graph Theory"},{"issue":"4","key":"S021819592250008XBIB044","first-page":"37:1","volume":"9","author":"Segal M.","year":"2013","journal-title":"ACM Trans. Sensor Networks"},{"key":"S021819592250008XBIB045","first-page":"363","volume-title":"Proc. Symposium on Theory of Computing","author":"Solomon S.","year":"2014"},{"key":"S021819592250008XBIB046","first-page":"281","volume-title":"Proc. ACM Symposium on Theory of Computing","author":"Talwar K.","year":"2004"},{"issue":"1","key":"S021819592250008XBIB047","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s10878-006-5980-0","volume":"11","author":"Wang Y.","year":"2006","journal-title":"J. Combin. Optim."}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819592250008X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T07:03:44Z","timestamp":1728543824000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S021819592250008X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9]]},"references-count":47,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.1142\/S021819592250008X"],"URL":"https:\/\/doi.org\/10.1142\/s021819592250008x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2022,9]]}}}