{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:05Z","timestamp":1775282285459,"version":"3.50.1"},"reference-count":26,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3791,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1016\/s0166-218x(02)00217-2","type":"journal-article","created":{"date-parts":[[2002,10,28]],"date-time":"2002-10-28T11:05:14Z","timestamp":1035803114000},"page":"55-82","source":"Crossref","is-referenced-by-count":15,"title":["An external memory data structure for shortest path queries"],"prefix":"10.1016","volume":"126","author":[{"given":"David","family":"Hutchinson","sequence":"first","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"Norbert","family":"Zeh","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00217-2_BIB1","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1137\/S0895480194272183","article-title":"Linear algorithms for partitioning embedded graphs of bounded genus","volume":"9","author":"Aleksandrov","year":"1996","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(02)00217-2_BIB2","doi-asserted-by":"crossref","unstructured":"L. Arge, The buffer tree: a new technique for optimal I\/O-algorithms, in: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 955, Springer, Berlin, 1995, pp. 334\u2013345.","DOI":"10.1007\/3-540-60220-8_74"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB3","unstructured":"Y.-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, J.S. Vitter, External-memory graph algorithms, in: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1995."},{"key":"10.1016\/S0166-218X(02)00217-2_BIB4","unstructured":"A. Crauser, K. Mehlhorn, U. Meyer, K\u00fcrzeste-Wege-Berechnung bei sehr gro\u00dfen Datenmengen, in: O. Spaniol (Ed.), Promotion tut not: Innovationsmotor \u201cGraduiertenkolleg\u201d, Aachener Beitr\u00e4ge zur Informatik, Vol. 21, Verlag der Augustinus Buchhandlung, 1997."},{"key":"10.1016\/S0166-218X(02)00217-2_BIB5","doi-asserted-by":"crossref","unstructured":"F. Dehne, W. Dittrich, D. Hutchinson, Efficient external memory algorithms by simulating coarse-grained parallel algorithms, in: Proceedings of the Ninth ACM Symposium on Parallel Algorithms and Architectures, 1997, pp. 106\u2013115.","DOI":"10.1145\/258492.258503"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB6","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connection with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"10.1016\/S0166-218X(02)00217-2_BIB7","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1006\/jagm.1993.1013","article-title":"Edge separators of planar and outerplanar graphs with applications","volume":"14","author":"Diks","year":"1993","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB8","doi-asserted-by":"crossref","unstructured":"H.N. Djidjev, Efficient algorithms for shortest path queries in planar digraphs, in: Proceedings of the 22nd Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Springer, Berlin, 1996, pp. 151\u2013165.","DOI":"10.1007\/3-540-62559-3_14"},{"issue":"6","key":"10.1016\/S0166-218X(02)00217-2_BIB9","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","article-title":"Fast algorithms for shortest paths in planar graphs, with applications","volume":"16","author":"Frederickson","year":"1987","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0166-218X(02)00217-2_BIB10","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1145\/102782.102788","article-title":"Planar graph decomposition and all pairs shortest paths","volume":"38","author":"Frederickson","year":"1991","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB11","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB12","doi-asserted-by":"crossref","unstructured":"H. Gazit, G.L. Miller, A parallel algorithm for finding a separator in planar graphs, in: Proceedings of the 28th Symposium on Foundations of Computer Science, 1987, pp. 238\u2013248.","DOI":"10.1109\/SFCS.1987.3"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB13","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, Planar separators and parallel polygon triangulation, in: Proceedings of the 24th ACM Symposium on Theory of Computing, 1992, pp. 507\u2013516.","DOI":"10.1145\/129712.129762"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB14","unstructured":"D. Hutchinson, A. Maheshwari, N. Zeh, An external memory data structure for shortest path queries, in: Proceedings of the Fifth ACM-SIAM Computing and Combinatorics Conference, Lecture Notes in Computer Science, Vol. 1627, Springer, Berlin, July 1999, pp. 51\u201360."},{"key":"10.1016\/S0166-218X(02)00217-2_BIB15","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Rao, M. Rauch, S. Subramanian, Faster shortest-path algorithms for planar graphs, in: Proceedings of the 26th ACM Symposium on Theory of Computing, May 1994, pp. 27\u201337.","DOI":"10.1145\/195058.195092"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB16","doi-asserted-by":"crossref","unstructured":"M. Lanthier, A. Maheshwari, J.-R. Sack, Approximating weighted shortest paths on polyhedral surfaces, in: Proceedings of the 13th Annual ACM Symposium on Computational Geometry, June 1997, pp. 274\u2013283.","DOI":"10.1145\/262839.262984"},{"issue":"2","key":"10.1016\/S0166-218X(02)00217-2_BIB17","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0166-218X(02)00217-2_BIB18","doi-asserted-by":"crossref","unstructured":"A. Maheshwari, N. Zeh, External memory algorithms for outerplanar graphs, in: Proceedings of the ISAAC\u201999, Lecture Notes in Computer Science, Springer, Berlin, December 1999, to appear.","DOI":"10.1007\/3-540-46632-0_31"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB19","unstructured":"K. Munagala, A. Ranade, I\/O-complexity of graph algorithms, in: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1999."},{"issue":"2","key":"10.1016\/S0166-218X(02)00217-2_BIB20","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01940646","article-title":"Blocking for external graph searching","volume":"16","author":"Nodine","year":"1996","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB21","series-title":"Computational Geometry\u2014An Introduction","author":"Preparata","year":"1985"},{"issue":"3","key":"10.1016\/S0166-218X(02)00217-2_BIB22","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/2.268881","article-title":"An introduction to disk drive modeling","volume":"27","author":"Ruemmler","year":"1994","journal-title":"IEEE Comput."},{"key":"10.1016\/S0166-218X(02)00217-2_BIB23","doi-asserted-by":"crossref","unstructured":"J.S. Vitter, External memory algorithms, in: Proceedings of the 17th Annual ACM Symposium on Principles of Database Systems, June 1998.","DOI":"10.1145\/275487.275501"},{"issue":"2\u20133","key":"10.1016\/S0166-218X(02)00217-2_BIB24","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/BF01185207","article-title":"Algorithms for parallel memory I: two-level memories","volume":"12","author":"Vitter","year":"1994","journal-title":"Algorithmica"},{"issue":"2\u20133","key":"10.1016\/S0166-218X(02)00217-2_BIB25","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01185208","article-title":"Algorithms for parallel memory II: hierarchical multilevel memories","volume":"12","author":"Vitter","year":"1994","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(02)00217-2_BIB26","unstructured":"N. Zeh, An external-memory data structure for shortest path queries, Diplomarbeit, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Friedrich-Schiller-Universit\u00e4t Jena, November 1998."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002172?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002172?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T05:12:48Z","timestamp":1580879568000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02002172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["S0166218X02002172"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00217-2","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}