{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T01:33:57Z","timestamp":1726191237328},"reference-count":14,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,5]],"date-time":"2006-10-05T00:00:00Z","timestamp":1160006400000},"content-version":"vor","delay-in-days":6427,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1989,3]]},"abstract":"Abstract<\/jats:title>Given a graph G = (V, E)<\/jats:italic>, a subgraph Gapos; = (V, Eapos;)<\/jats:italic> is a t\u2010spanner<\/jats:italic> of G<\/jats:italic> if for every u, v \u2208 V<\/jats:italic>, the distance from u<\/jats:italic> to v<\/jats:italic> in Gapos;<\/jats:italic> is at most t<\/jats:italic> times longer than that distance in G.<\/jats:italic> This paper presents some results concerning the existence and efficient constructability of sparse spanners for various classes of graphs, including general undirected graphs, undirected chordal graphs, and general directed graphs.<\/jats:p>","DOI":"10.1002\/jgt.3190130114","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T12:16:45Z","timestamp":1180181805000},"page":"99-116","source":"Crossref","is-referenced-by-count":399,"title":["Graph spanners"],"prefix":"10.1002","volume":"13","author":[{"given":"David","family":"Peleg","sequence":"first","affiliation":[]},{"given":"Alejandro A.","family":"Sch\u00e4ffer","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,5]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"S.Bhatt F.Chung F.Leighton andA.Rosenberg Optimal simulations of tree machines.27th IEEE Symposium on the Foundations of Computer Science Toronto (1986)274\u2013282.","DOI":"10.1109\/SFCS.1986.38"},{"key":"e_1_2_1_4_2","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s B.","year":"1978"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90002-8"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"L. P.Chew There is a planar graph almost as good as the complete graph.Proceedings of the 2nd ACM Symposium on Computational Geometry Yorktown Heights NY (1986)169\u2013177.","DOI":"10.1145\/10515.10534"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"D. P.Dobkin S. J.Friedman andK. J.Supowit Delaunay graphs are almost as good as complete graphs.28th IEEE Symposium on the Foundations of Computer Science Los Angeles (1987)20\u201326.","DOI":"10.1109\/SFCS.1987.18"},{"key":"e_1_2_1_8_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0605032"},{"key":"e_1_2_1_11_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"e_1_2_1_12_2","volume-title":"An Introduction to the Theory of Numbers","author":"Niven I.","year":"1972"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"D.PelegandJ. D.Ullman An optimal synchronizer for the hypercube.6th ACM Symposium on Principles of Distributed Computing Vancouver (1987)77\u201385.","DOI":"10.1145\/41840.41847"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"D.PelegandE.Upfal A tradeoff between space and efficiency for routing tables.20th ACM Symposium on the Theory of Computing Chicago (1988)43\u201352.","DOI":"10.1145\/62212.62217"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190130114","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190130114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T16:52:21Z","timestamp":1697907141000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190130114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,3]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,3]]}},"alternative-id":["10.1002\/jgt.3190130114"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190130114","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,3]]}}}