{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T05:59:21Z","timestamp":1715061561724},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1991,6]]},"abstract":"<jats:p> Given a connected graph G=(V,E) with positive edge weights, define the distance d<jats:sub>G<\/jats:sub>(u,v) between vertices u and v to be the length of a shortest path from u to v in G. A spanning subgraph G' of G is said to be a t-spanner for G if, for every pair of vertices u and v, d<jats:sub>G'<\/jats:sub>(u,v)\u2264t\u00b7d<jats:sub>G<\/jats:sub>(u,v). Consider a complete graph G whose vertex set is a set of n points in [Formula: see text] and whose edge weights are given by the L<jats:sub>p<\/jats:sub> distance between respective points. Given input parameter \u220a, 0&lt;\u220a\u22641, we show how to construct a (1+\u220a)-spanner for G containing [Formula: see text] edges in [Formula: see text] time. We apply this spanner to the construction of approximate minimum spanning trees. <\/jats:p>","DOI":"10.1142\/s0218195991000098","type":"journal-article","created":{"date-parts":[[2004,11,26]],"date-time":"2004-11-26T20:43:01Z","timestamp":1101501781000},"page":"99-107","source":"Crossref","is-referenced-by-count":46,"title":["CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS"],"prefix":"10.1142","volume":"01","author":[{"given":"JEFFERY S.","family":"SALOWE","sequence":"first","affiliation":[{"name":"Department of Computer Science,  University of Virginia, Thornton Hall,  Charlottesville, Virginia 22903, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195991000098","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:33:37Z","timestamp":1565116417000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195991000098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[1991,6]]}},"alternative-id":["10.1142\/S0218195991000098"],"URL":"https:\/\/doi.org\/10.1142\/s0218195991000098","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}