{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:21:58Z","timestamp":1772083318516,"version":"3.50.1"},"reference-count":70,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1137\/110826655","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T10:39:07Z","timestamp":1352803147000},"page":"1380-1425","source":"Crossref","is-referenced-by-count":21,"title":["Transitive-Closure Spanners"],"prefix":"10.1137","volume":"41","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyomin","family":"Jung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","reference":[{"key":"atypb1","first-page":"188","author":"Abraham I.","year":"2006","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0201008"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"atypb7","first-page":"489","author":"Arya S.","year":"1995","journal-title":"New York"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1455526.1455531"},{"key":"atypb9","first-page":"11","author":"Atallah M. J.","year":"2006","journal-title":"New York"},{"key":"atypb10","first-page":"190","author":"Atallah M. J.","year":"2005","journal-title":"New York"},{"key":"atypb11","first-page":"272","author":"Awerbuch B.","year":"1985","journal-title":"New York"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"atypb13","first-page":"760","author":"Berman P.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb14","first-page":"1","author":"Berman P.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb16","first-page":"424","author":"Berman P.","year":"2010","journal-title":"Germany"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/100808186"},{"key":"atypb18","first-page":"932","author":"Bhattacharyya A.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb19","first-page":"111","volume":"1","author":"Bodlaender H. L.","year":"1994","journal-title":"Nordic J. Comput."},{"key":"atypb20","first-page":"109","author":"Chandra A. K.","year":"1983","journal-title":"Heidelberg"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90015-7"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840366"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921664"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.08.001"},{"key":"atypb28","first-page":"323","author":"Dinitz M.","year":"2011","journal-title":"New York"},{"key":"atypb29","first-page":"97","author":"Dodis Y.","year":"1999","journal-title":"Berlin"},{"key":"atypb30","first-page":"750","author":"Dodis Y.","year":"1999","journal-title":"New York"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"atypb33","first-page":"636","author":"Elkin M.","year":"2000","journal-title":"Berlin"},{"key":"atypb34","first-page":"117","author":"Elkin M.","year":"2001","journal-title":"Canada"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.022"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1266-2"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb40","first-page":"922","author":"Feldman M.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"atypb42","first-page":"474","author":"Fischer E.","year":"2002","journal-title":"New York"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb46","first-page":"721","author":"Halevy S.","year":"2004","journal-title":"Berlin"},{"key":"atypb47","first-page":"665","author":"Hesse W.","year":"2003","journal-title":"Philadelphia"},{"key":"atypb49","first-page":"433","author":"Jha M.","year":"2011","journal-title":"Proceedings of the FOCS"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0021-y"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268753"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb54","first-page":"286","author":"Lund C.","year":"1993","journal-title":"New York"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"atypb61","first-page":"167","author":"Raskhodnikova S.","year":"2010","journal-title":"Heidelberg"},{"key":"atypb62","first-page":"475","author":"Raz R.","year":"1997","journal-title":"New York"},{"key":"atypb63","first-page":"844","author":"Roditty L.","year":"2002","journal-title":"Philadelphia"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"atypb65","first-page":"371","author":"Santis A. De","year":"2007","journal-title":"Berlin"},{"key":"atypb66","first-page":"820","author":"Solomon S.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb67","first-page":"48","author":"Solomon S.","year":"2010","journal-title":"Berlin"},{"key":"atypb68","first-page":"205","author":"Thorup M.","year":"1993","journal-title":"Berlin"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001668"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0829"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"atypb72","first-page":"1","author":"Thorup M.","year":"2001","journal-title":"New York"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"atypb74","first-page":"389","author":"Woodruff D. P.","year":"2006","journal-title":"NJ"},{"key":"atypb75","first-page":"128","author":"A.","year":"1982","journal-title":"New York"},{"key":"atypb76","first-page":"33","author":"Zwick U.","year":"2001","journal-title":"Berlin"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110826655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,1,29]],"date-time":"2017-01-29T09:27:32Z","timestamp":1485682052000},"score":1,"resource":{"primary":{"URL":"http:\/\/epubs.siam.org\/doi\/10.1137\/110826655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":70,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/110826655"],"URL":"https:\/\/doi.org\/10.1137\/110826655","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}