{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:13:40Z","timestamp":1766135620532},"reference-count":0,"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":[[1996,6]]},"abstract":"<jats:p> Let V be any set of n points in k-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for all u and \u03c5 in V, the length of the shortest path from u to \u03c5 in the spanner is at most t times the Euclidean distance between u and \u03c5. We show that for any \u03b4&gt;1, there exists a t-spanner (where t is a constant that depends only on \u03b4 and k) with the following properties: its maximum degree is 3, it has at most n\u00b7\u03b4 edges, its total edge weight is at most O(1) times the weight of the minimum spanning tree of V, and it can be constructed in O(n log n) time. The constants implicit in the O-notation depend on \u03b4 and k. <\/jats:p>","DOI":"10.1142\/s0129054196000105","type":"journal-article","created":{"date-parts":[[2004,9,6]],"date-time":"2004-09-06T11:50:09Z","timestamp":1094471409000},"page":"121-135","source":"Crossref","is-referenced-by-count":19,"title":["CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES"],"prefix":"10.1142","volume":"07","author":[{"given":"GAUTAM","family":"DAS","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PAUL J.","family":"HEFFERNAN","sequence":"additional","affiliation":[{"name":"15 Deerfield Road, New Providence, NJ 07974, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054196000105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:43:02Z","timestamp":1565138582000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054196000105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1996,6]]}},"alternative-id":["10.1142\/S0129054196000105"],"URL":"https:\/\/doi.org\/10.1142\/s0129054196000105","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,6]]}}}