{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T03:12:15Z","timestamp":1764645135189,"version":"3.38.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T00:00:00Z","timestamp":1322611200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s00453-011-9598-y","type":"journal-article","created":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T19:28:24Z","timestamp":1322681304000},"page":"409-442","source":"Crossref","is-referenced-by-count":13,"title":["Streaming Graph Computations with a Helpful Advisor"],"prefix":"10.1007","volume":"65","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,11,30]]},"reference":[{"key":"9598_CR1","first-page":"540","volume-title":"FOCS","author":"G. Aggarwal","year":"2004","unstructured":"Aggarwal, G., Datar, M., Rajagopalan, S., Ruhl, M.: On the streaming model augmented with a sorting primitive. In: FOCS, pp. 540\u2013549 (2004)"},{"key":"9598_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity\u2014A Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity\u2014A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"9598_CR3","volume-title":"Convex Optimization Theory","author":"D. Bertsekas","year":"2009","unstructured":"Bertsekas, D.: Convex Optimization Theory. Athena Scientific, Nashua (2009)"},{"doi-asserted-by":"crossref","unstructured":"Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica 90\u201399 (1995)","key":"9598_CR4","DOI":"10.1109\/SFCS.1991.185352"},{"issue":"8","key":"9598_CR5","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"E. Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"issue":"7","key":"9598_CR6","doi-asserted-by":"crossref","first-page":"2829","DOI":"10.1109\/TIT.2008.924688","volume":"54","author":"E.J. Cand\u00e8s","year":"2008","unstructured":"Cand\u00e8s, E.J., Randall, P.A.: Highly robust error correction by convex programming. IEEE Trans. Inf. Theory 54(7), 2829\u20132840 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9598_CR7","first-page":"222","volume-title":"ICALP","author":"A. Chakrabarti","year":"2009","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A.: Annotations in data streams. In: ICALP, pp. 222\u2013234 (2009)"},{"key":"9598_CR8","first-page":"205","volume-title":"STOC","author":"K.L. Clarkson","year":"2009","unstructured":"Clarkson, K.L., Woodruff, D.P.: Numerical linear algebra in the streaming model. In: STOC, pp. 205\u2013214 (2009)"},{"key":"9598_CR9","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/978-3-642-02017-9_21","volume-title":"Theory and Applications of Models of Computation","author":"A. Das\u00a0Sarma","year":"2009","unstructured":"Das\u00a0Sarma, A., Lipton, R.J., Nanongkai, D.: Best-order streaming model. In: Theory and Applications of Models of Computation, pp. 178\u2013191 (2009)"},{"doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. ACM Trans. Algorithms 6(1) (2009)","key":"9598_CR10","DOI":"10.1145\/1644015.1644021"},{"issue":"2","key":"9598_CR11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Hochbaum, D.S.: Personal communication (2011)","key":"9598_CR12"},{"key":"9598_CR13","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1145\/96559.96597","volume":"37","author":"D.S. Hochbaum","year":"1990","unstructured":"Hochbaum, D.S., Shanthikumar, J.G.: Convex separable optimization is not much harder than linear optimization. J. ACM 37, 843\u2013862 (1990)","journal-title":"J. ACM"},{"issue":"2","key":"9598_CR14","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02526037","volume":"18","author":"V. King","year":"1997","unstructured":"King, V.: A simpler minimum spanning tree verification algorithm. Algorithmica 18(2), 263\u2013270 (1997)","journal-title":"Algorithmica"},{"key":"9598_CR15","volume-title":"Algorithm Design","author":"J.M. Kleinberg","year":"2006","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Algorithm Design. Addison-Wesley, Reading (2006)"},{"unstructured":"Lipton, R.J.: Fingerprinting sets. Technical Report Cs-tr-212-89, Princeton University (1989)","key":"9598_CR16"},{"key":"9598_CR17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/3-540-52282-4_44","volume-title":"STACS","author":"R.J. Lipton","year":"1990","unstructured":"Lipton, R.J.: Efficient checking of computations. In: STACS, pp. 207\u2013215 (1990)"},{"key":"9598_CR18","volume-title":"Encycl. of Database Systems","author":"A. McGregor","year":"2009","unstructured":"McGregor, A.: Graph Mining on Streams. In: Encycl. of Database Systems. Springer, Berlin (2009)"},{"key":"9598_CR19","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Upper Saddle River (1982)"},{"key":"9598_CR20","volume-title":"IEEE FOCS","author":"T. Sarlos","year":"2006","unstructured":"Sarlos, T.: Improved approximation algorithms for large matrices via random projections. In: IEEE FOCS, 2006"},{"key":"9598_CR21","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)"},{"key":"9598_CR22","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics)","author":"A. Schrijver","year":"2004","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics). Springer, Berlin (2004)"},{"key":"9598_CR23","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9598_CR24","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250\u2013256 (1986)","journal-title":"Oper. Res."},{"key":"9598_CR25","volume-title":"ICDE","author":"M. Yiu","year":"2010","unstructured":"Yiu, M., Lin, Y., Mouratidis, K.: Efficient verification of shortest path search via authenticated hints. In: ICDE, 2010"},{"key":"9598_CR26","volume-title":"CoRR","author":"R. Yuster","year":"2010","unstructured":"Yuster, R.: Computing the diameter polynomially faster than APSP. In: CoRR (2010). arXiv: 1011.6181v2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9598-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9598-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9598-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T16:59:48Z","timestamp":1741971588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9598-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,30]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["9598"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9598-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2011,11,30]]}}}