{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:32Z","timestamp":1759637612457},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,2,8]],"date-time":"2014-02-08T00:00:00Z","timestamp":1391817600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1007\/s00493-014-2833-9","type":"journal-article","created":{"date-parts":[[2014,2,8]],"date-time":"2014-02-08T06:33:05Z","timestamp":1391841185000},"page":"255-277","source":"Crossref","is-referenced-by-count":4,"title":["Steiner transitive-closure spanners of low-dimensional posets"],"prefix":"10.1007","volume":"34","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnab","family":"Bhattacharyya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Grigorescu","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"}]},{"given":"Grigory","family":"Yaroslavtsev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,2,8]]},"reference":[{"key":"2833_CR1","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/BF01459088","volume":"999","author":"W Ackermann","year":"1928","unstructured":"W. Ackermann: Zum hilbertschen Aufbau der reellen Zahlen, Math. Ann. 999 (1928), 118\u2013133.","journal-title":"Math. Ann."},{"key":"2833_CR2","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/s00453-007-9075-9","volume":"951","author":"N Ailon","year":"2008","unstructured":"N. Ailon, B. Chazelle, S. Comandur and D. Liu: Property-preserving data reconstruction, Algorithmica 951 (2008), 160\u2013182.","journal-title":"Algorithmica"},{"key":"2833_CR3","volume-title":"Technical Report 71\/87","author":"N Alon","year":"1987","unstructured":"N. Alon and B. Schieber: Optimal preprocessing for answering on-line product queries, Technical Report 71\/87, Tel-Aviv University, 1987."},{"key":"2833_CR4","doi-asserted-by":"crossref","unstructured":"M. J. Atallah, M. Blanton, N. Fazio and K. B. Frikken: Dynamic and efficient key management for access hierarchies, ACM Trans. Inf. Syst. Secur. 912 2009.","DOI":"10.1145\/1455526.1455531"},{"key":"2833_CR5","first-page":"190","volume-title":"ACM Conference on Computer and Communications Security","author":"M J Atallah","year":"2005","unstructured":"M. J. Atallah, K. B. Frikken and M. Blanton: Dynamic and efficient key management for access hierarchies, in V. Atluri, C. Meadows, and A. Juels, editors, ACM Conference on Computer and Communications Security, 190\u2013202, ACM, 2005."},{"key":"2833_CR6","first-page":"272","volume-title":"PODC","author":"B Awerbuch","year":"1985","unstructured":"B. Awerbuch: Communication-time trade-offs in network synchronization, in: PODC, 272\u2013276, 1985."},{"key":"2833_CR7","first-page":"760","volume-title":"ICALP (1), volume 6755 of Lecture Notes in Computer Science","author":"P Berman","year":"2011","unstructured":"P. Berman, A. Bhattacharyya, E. Grigorescu, S. Raskhodnikova, D. P. Woodruff and G. Yaroslavtsev: Steiner transitive-closure spanners of low-dimensional posets, in: L. Aceto, M. Henzinger, and J. Sgall, editors, ICALP (1), volume 6755 of Lecture Notes in Computer Science, 760\u2013772, Springer, 2011."},{"key":"2833_CR8","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/100808186","volume":"926","author":"A Bhattacharyya","year":"2012","unstructured":"A. Bhattacharyya, E. Grigorescu, M. Jha, K. Jung, S. Raskhodnikova and D. P. Woodruff: Lower bounds for local monotonicity reconstruction from transitive-closure spanners, SIAM J. Discrete Math. 926 (2012), 618\u2013646.","journal-title":"SIAM J. Discrete Math."},{"key":"2833_CR9","doi-asserted-by":"crossref","first-page":"1380","DOI":"10.1137\/110826655","volume":"941","author":"A Bhattacharyya","year":"2012","unstructured":"A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova and D. P. Woodruff: Transitive-closure spanners, SIAM J. Comput. 941 (2012), 1380\u20131425.","journal-title":"SIAM J. Comput."},{"key":"2833_CR10","first-page":"111","volume":"91","author":"H L Bodlaender","year":"1994","unstructured":"H. L. Bodlaender, G. Tel and N. Santoro: Trade-offs in non-reversing diameter, Nordic J. of Computing 91 (1994) 111\u2013134.","journal-title":"Nordic J. of Computing"},{"key":"2833_CR11","first-page":"109","volume-title":"ICALP, volume 154 of LNCS","author":"A K Chandra","year":"1983","unstructured":"A. K. Chandra, S. Fortune and R. J. Lipton: Lower bounds for constant depth circuits for prefix problems, in: J. D\u00edaz, editor, ICALP, volume 154 of LNCS, 109\u2013117, Springer, 1983."},{"key":"2833_CR12","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/0022-0000(85)90015-7","volume":"930","author":"A K Chandra","year":"1985","unstructured":"A. K. Chandra, S. Fortune and R. J. Lipton: Unbounded fan-in circuits and associative functions, J. Comput. Syst. Sci. 930 (1985), 222\u2013234.","journal-title":"J. Comput. Syst. Sci."},{"key":"2833_CR13","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF01840366","volume":"92","author":"B Chazelle","year":"1987","unstructured":"B. Chazelle: Computing on a free tree via complexity-preserving mappings, Algorithmica 92 (1987), 337\u2013361.","journal-title":"Algorithmica"},{"key":"2833_CR14","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.tcs.2008.05.021","volume":"9407","author":"A Santis De","year":"2008","unstructured":"A. De Santis, A. L. Ferrara and B. Masucci: New constructions for provably-secure time-bound hierarchical key assignment schemes, Theor. Comput. Sci. 9407 (2008), 213\u2013230.","journal-title":"Theor. Comput. Sci."},{"key":"2833_CR15","first-page":"97","volume-title":"RANDOM","author":"Y Dodis","year":"1999","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron and A. Samorodnitsky: Improved testing algorithms for monotonicity, in: RANDOM, 97\u2013108, 1999."},{"key":"2833_CR16","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1090\/S0002-9904-1940-07213-1","volume":"946","author":"B Dushnik","year":"1940","unstructured":"B. Dushnik and E. Miller: Concerning similarity transformations of linearly ordered sets, Bulletin Amer. Math. Soc. 946 (1940), 322\u2013326.","journal-title":"Bulletin Amer. Math. Soc."},{"key":"2833_CR17","doi-asserted-by":"crossref","first-page":"600","DOI":"10.2307\/2371374","volume":"963","author":"B Dushnik","year":"1941","unstructured":"B. Dushnik and E. W. Miller: Partially ordered sets, Amer. J. Math. 963 (1941), 600\u2013610.","journal-title":"Amer. J. Math."},{"key":"2833_CR18","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00403406","volume":"93","author":"Z F\u00fcredi","year":"1986","unstructured":"Z. F\u00fcredi and J. Kahn: On the dimension of ordered sets of bounded degree, Order 93 (1986), 15\u201320.","journal-title":"Order"},{"key":"2833_CR19","first-page":"665","volume-title":"SODA","author":"W Hesse","year":"2003","unstructured":"W. Hesse: Directed graphs requiring large numbers of shortcuts, in: SODA, 665\u2013669, ACM\/SIAM, 2003."},{"key":"2833_CR20","first-page":"77","volume":"91","author":"T Hiraguchi","year":"1951","unstructured":"T. Hiraguchi: On the dimension of partially ordered sets, Science Reports Kanazawa University 91 (1951), 77\u201394.","journal-title":"Science Reports Kanazawa University"},{"key":"2833_CR21","first-page":"433","volume-title":"FOCS","author":"M Jha","year":"2011","unstructured":"M. Jha and S. Raskhodnikova: Testing and reconstruction of Lipschitz functions with applications to data privacy, in: R. Ostrovsky, editor, FOCS, 433\u2013442, IEEE, 2011."},{"key":"2833_CR22","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0012-365X(81)90203-X","volume":"935","author":"D Kelly","year":"1981","unstructured":"D. Kelly: On the dimension of partially ordered sets, Discrete Mathematics 935 (1981), 135\u2013156.","journal-title":"Discrete Mathematics"},{"key":"2833_CR23","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"913","author":"D Peleg","year":"1989","unstructured":"D. Peleg and A. A. Sch\u00e4affer: Graph spanners, J. Graph Theory 913 (1989), 99\u2013116.","journal-title":"J. Graph Theory"},{"key":"2833_CR24","first-page":"167","volume-title":"Property Testing, volume 6390 of LNCS","author":"S Raskhodnikova","year":"2010","unstructured":"S. Raskhodnikova: Transitive-closure spanners: A survey, in: O. Goldreich, editor, Property Testing, volume 6390 of LNCS, 167\u2013196, Springer, 2010."},{"key":"2833_CR25","doi-asserted-by":"crossref","first-page":"2897","DOI":"10.1137\/080728561","volume":"939","author":"M E Saks","year":"2010","unstructured":"M. E. Saks and C. Seshadhri: Local monotonicity reconstruction, SIAM J. Comput. 939 (2010), 2897\u20132926.","journal-title":"SIAM J. Comput."},{"key":"2833_CR26","first-page":"205","volume-title":"WG, volume 657 of LNCS","author":"M Thorup","year":"1992","unstructured":"M. Thorup: On shortcutting digraphs, in: E. W. Mayr, editor, WG, volume 657 of LNCS, 205\u2013211, Springer, 1992."},{"key":"2833_CR27","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1017\/S0963548300001668","volume":"94","author":"M Thorup","year":"1995","unstructured":"M. Thorup: Shortcutting planar digraphs, Combinatorics, Probability & Computing 94 (1995), 287\u2013315.","journal-title":"Combinatorics, Probability & Computing"},{"key":"2833_CR28","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1006\/jagm.1996.0829","volume":"923","author":"M Thorup","year":"1997","unstructured":"M. Thorup: Parallel shortcutting of rooted trees, J. Algorithms 923 (1997), 139\u2013159.","journal-title":"J. Algorithms"},{"key":"2833_CR29","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/0095-8956(77)90048-X","volume":"922","author":"W T Trotter","year":"1977","unstructured":"W. T. Trotter and J. Moore: The dimension of planar posets, Journal of Combinatorial Theory, Series B 922 (1977), 54\u201367.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2833_CR30","first-page":"351","volume":"93","author":"M Yannakakis","year":"1982","unstructured":"M. Yannakakis: The complexity of the partial order dimension problem, SIAM Journal on Matrix Analysis and Applications 93 (1982), 351\u2013358.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"2833_CR31","first-page":"128","volume-title":"STOC","author":"A C-C Yao","year":"1982","unstructured":"A. C.-C. Yao: Space-time tradeoff for answering range queries (extended abstract), in: H. R. Lewis, B. B. Simons, W. A. Burkhard, and L. H. Landweber, editors, STOC, 128\u2013136, ACM, 1982."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2833-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-2833-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2833-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:13:31Z","timestamp":1565183611000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-2833-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,8]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["2833"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-2833-9","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2,8]]}}}