{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:15:39Z","timestamp":1781259339780,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":60,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642163661","type":"print"},{"value":"9783642163678","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_10","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T11:25:55Z","timestamp":1286450755000},"page":"167-196","source":"Crossref","is-referenced-by-count":7,"title":["Transitive-Closure Spanners: A Survey"],"prefix":"10.1007","author":[{"given":"Sofya","family":"Raskhodnikova","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: PODC, pp. 188\u2013197 (2006)","DOI":"10.1145\/1146381.1146411"},{"issue":"2","key":"10_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"A.V. Aho","year":"1972","unstructured":"Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput.\u00a01(2), 131\u2013137 (1972)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10_CR3","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/s00453-007-9075-9","volume":"51","author":"N. Ailon","year":"2008","unstructured":"Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Property-preserving data reconstruction. Algorithmica\u00a051(2), 160\u2013182 (2008)","journal-title":"Algorithmica"},{"issue":"11","key":"10_CR4","doi-asserted-by":"publisher","first-page":"1704","DOI":"10.1016\/j.ic.2006.06.001","volume":"204","author":"N. Ailon","year":"2006","unstructured":"Ailon, N., Chazelle, B.: Information theory in property testing and monotonicity testing in higher dimension. Inf. Comput.\u00a0204(11), 1704\u20131717 (2006)","journal-title":"Inf. Comput."},{"key":"10_CR5","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Tech. Rep. 71\/87, Tel-Aviv University (1987)"},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09(1), 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"issue":"3","key":"10_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1455526.1455531","volume":"12","author":"M.J. Atallah","year":"2009","unstructured":"Atallah, M.J., Blanton, M., Fazio, N., Frikken, K.B.: Dynamic and efficient key management for access hierarchies. ACM Trans. Inf. Syst. Secur.\u00a012(3), 1\u201343 (2009)","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Atallah, M.J., Blanton, M., Frikken, K.B.: Key management for non-tree access hierarchies. In: SACMAT, pp. 11\u201318 (2006)","DOI":"10.1145\/1133058.1133062"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Atallah, M.J., Frikken, K.B., Blanton, M.: Dynamic and efficient key management for access hierarchies. In: ACM Conference on Computer and Communications Security, pp. 190\u2013202 (2005)","DOI":"10.1145\/1102120.1102147"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Awerbuch, B.: Communication-time trade-offs in network synchronization. In: PODC, pp. 272\u2013276 (1985)","DOI":"10.1145\/323596.323621"},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S. Baswana","year":"2006","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected $\\tilde{O} (n^2)$ time. ACM Transactions on Algorithms\u00a02(4), 557\u2013577 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"10_CR12","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.ic.2004.10.001","volume":"196","author":"T. Batu","year":"2005","unstructured":"Batu, T., Rubinfeld, R., White, P.: Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput.\u00a0196(1), 42\u201356 (2005)","journal-title":"Inf. Comput."},{"key":"10_CR13","unstructured":"Berman, P., Raskhodnikova, S., Ruan, G.: Finding sparser directed spanners (2010) (manuscript)"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Jha, M., Jung, K., Raskhodnikova, S., Woodruff, D.: Lower bounds for local monotonicity reconstruction from transitive-closure spanners. In: RANDOM (2010)","DOI":"10.1007\/978-3-642-15369-3_34"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.: Transitive-closure spanners. In: SODA, pp. 932\u2013941 (2009)","DOI":"10.1137\/1.9781611973068.101"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.: Transitive-closure spanners of the hypercube and the hypergrid (2009), eCCC Report TR09-046","DOI":"10.1137\/1.9781611973068.101"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Raskhodnikova, S., Woodruff, D.: Steiner transitive-closure spanners of d-dimensional posets (2010) (manuscript)","DOI":"10.1137\/1.9781611973068.101"},{"issue":"1","key":"10_CR18","first-page":"111","volume":"1","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Tel, G., Santoro, N.: Tradeoffs in non-reversing diameter. Nordic Journal of Computing\u00a01(1), 111\u2013134 (1994)","journal-title":"Nordic Journal of Computing"},{"key":"10_CR19","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01840366","volume":"2","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B.: Computing on a free tree via complexity-preserving mappings. Algorithmica\u00a02, 337\u2013361 (1987)","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput.\u00a028(1), 210\u2013236 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR21","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/331605.331610","volume":"47","author":"E. Cohen","year":"2000","unstructured":"Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. JACM\u00a047(1), 132\u2013166 (2000)","journal-title":"JACM"},{"issue":"1","key":"10_CR22","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L. Cowen","year":"2001","unstructured":"Cowen, L.: Compact routing with minimum stretch. J. Algorithms\u00a038(1), 170\u2013183 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"10_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jalgor.2003.08.001","volume":"50","author":"L. Cowen","year":"2004","unstructured":"Cowen, L., Wagner, C.G.: Compact roundtrip routing in directed networks. J. Algorithms\u00a050(1), 79\u201395 (2004)","journal-title":"J. Algorithms"},{"issue":"1","key":"10_CR24","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R.P. Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. The Annals of Mathematics, Second Series\u00a051(1), 161\u2013166 (1950)","journal-title":"The Annals of Mathematics, Second Series"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-540-48413-4_10","volume-title":"Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques","author":"Y. Dodis","year":"1999","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol.\u00a01671, pp. 97\u2013108. Springer, Heidelberg (1999)"},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1090\/S0002-9904-1940-07213-1","volume":"46","author":"B. Dushnik","year":"1940","unstructured":"Dushnik, B., Miller, E.: Concerning similarity transformations of linearly ordered sets. Bulletin Amer. Math. Soc.\u00a046, 322\u2013326 (1940)","journal-title":"Bulletin Amer. Math. Soc."},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Computing almost shortest paths. In: PODC, pp. 53\u201362 (2001)","DOI":"10.1145\/383962.383983"},{"key":"10_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1007\/3-540-45022-X_54","volume-title":"Automata, Languages and Programming","author":"M. Elkin","year":"2000","unstructured":"Elkin, M., Peleg, D.: Strong inapproximability of the basic k-spanner problem. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 636\u2013647. Springer, Heidelberg (2000)"},{"key":"10_CR29","unstructured":"Elkin, M., Peleg, D.: The client-server 2-spanner problem with applications to network design. In: SIROCCO, pp. 117\u2013132 (2001)"},{"issue":"4","key":"10_CR30","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s00224-006-1266-2","volume":"41","author":"M. Elkin","year":"2007","unstructured":"Elkin, M., Peleg, D.: The hardness of approximating spanner problems. Theory Comput. Syst.\u00a041(4), 691\u2013729 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"10_CR31","first-page":"717","volume":"60","author":"F. Ergun","year":"2000","unstructured":"Ergun, F., Kannan, S., Kumar, S.R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. JCSS\u00a060(3), 717\u2013751 (2000)","journal-title":"JCSS"},{"issue":"1","key":"10_CR32","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ic.2003.09.003","volume":"189","author":"E. Fischer","year":"2004","unstructured":"Fischer, E.: On the strength of comparisons in property testing. Inf. Comput.\u00a0189(1), 107\u2013116 (2004)","journal-title":"Inf. Comput."},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: STOC, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"issue":"4","key":"10_CR34","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. JACM\u00a045(4), 653\u2013750 (1998)","journal-title":"JACM"},{"issue":"3","key":"10_CR35","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica\u00a020(3), 301\u2013337 (2000)","journal-title":"Combinatorica"},{"key":"10_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/978-3-540-27836-8_61","volume-title":"Automata, Languages and Programming","author":"S. Halevy","year":"2004","unstructured":"Halevy, S., Kushilevitz, E.: Testing monotonicity over graph products. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 721\u2013732. Springer, Heidelberg (2004)"},{"key":"10_CR37","unstructured":"Hesse, W.: Directed graphs requiring large numbers of shortcuts. In: SODA, pp. 665\u2013669 (2003)"},{"key":"10_CR38","volume-title":"Approximation Algorithms for NP-hard Problems","year":"1997","unstructured":"Hochbaum, D. (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston (1997)"},{"key":"10_CR39","doi-asserted-by":"crossref","unstructured":"Jha, M., Raskhodnikova, S.: Testing and reconstruction of lipschitz functions with applications to data privacy (2010) (manuscript)","DOI":"10.1109\/FOCS.2011.13"},{"issue":"3","key":"10_CR40","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/s00453-001-0021-y","volume":"30","author":"G. Kortsarz","year":"2001","unstructured":"Kortsarz, G.: On the hardness of approximating spanners. Algorithmica\u00a030(3), 432\u2013450 (2001)","journal-title":"Algorithmica"},{"issue":"2","key":"10_CR41","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036(2), 177\u2013189 (1979), http:\/\/www.jstor.org\/stable\/2100927","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"10_CR42","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed computing: a locality-sensitive approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"issue":"1","key":"10_CR43","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. Journal of Graph Theory\u00a013(1), 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"10_CR44","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput.\u00a018(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10_CR45","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. JACM\u00a036(3), 510\u2013530 (1989)","journal-title":"JACM"},{"key":"10_CR46","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: SODA, pp. 844\u2013851 (2002)"},{"issue":"2","key":"10_CR47","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR48","unstructured":"Saks, M.E., Seshadhri, C.: Parallel monotonicity reconstruction. In: Proceedings of the 19th Annual Symposium on Discrete Algorithms (SODA), pp. 962\u2013971 (2008)"},{"key":"10_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-540-74456-6_34","volume-title":"Mathematical Foundations of Computer Science 2007","author":"A.D. Santis","year":"2007","unstructured":"Santis, A.D., Ferrara, A.L., Masucci, B.: Efficient provably-secure hierarchical key assignment schemes. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 371\u2013382. Springer, Heidelberg (2007)"},{"key":"10_CR50","unstructured":"Seidel, R.: Understanding the inverse Ackermann function (2006), http:\/\/cgi.di.uoa.gr\/~ewcg06\/invited\/Seidel.pdf"},{"key":"10_CR51","unstructured":"Soriano, D.G., Matsliah, A., Chakraborty, S., Briet, J.: Monotonicity testing and shortest-path routing on the cube (2010), eCCC Report TR10-048"},{"key":"10_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-56402-0_48","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Thorup","year":"1993","unstructured":"Thorup, M.: On shortcutting digraphs. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol.\u00a0657, pp. 205\u2013211. Springer, Heidelberg (1993)"},{"key":"10_CR53","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1017\/S0963548300001668","volume":"4","author":"M. Thorup","year":"1995","unstructured":"Thorup, M.: Shortcutting planar digraphs. Combinatorics, Probability & Computing\u00a04, 287\u2013315 (1995)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"1","key":"10_CR54","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1006\/jagm.1996.0829","volume":"23","author":"M. Thorup","year":"1997","unstructured":"Thorup, M.: Parallel shortcutting of rooted trees. J. Algorithms\u00a023(1), 139\u2013159 (1997)","journal-title":"J. Algorithms"},{"key":"10_CR55","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: ACM Symposium on Parallel Algorithms and Architectures, pp. 1\u201310 (2001), http:\/\/citeseer.ist.psu.edu\/thorup01compact.html","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"10_CR56","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. JACM\u00a052(1), 1\u201324 (2005)","journal-title":"JACM"},{"key":"10_CR57","volume-title":"Combinatorics and Partially Ordered Sets: Dimension Theory","year":"1992","unstructured":"Trotter, W. (ed.): Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore (1992)"},{"key":"10_CR58","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Lower bounds for additive spanners, emulators, and more. In: FOCS, pp. 389\u2013398 (2006)","DOI":"10.1109\/FOCS.2006.45"},{"issue":"3","key":"10_CR59","first-page":"351","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. JMAA\u00a03(3), 351\u2013358 (1982)","journal-title":"JMAA"},{"key":"10_CR60","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Space-time tradeoff for answering range queries (extended abstract). In: STOC, pp. 128\u2013136 (1982)","DOI":"10.1145\/800070.802185"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T05:10:59Z","timestamp":1559711459000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":60,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}