{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T05:18:55Z","timestamp":1777439935034,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1995,10,1]],"date-time":"1995-10-01T00:00:00Z","timestamp":812505600000},"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":[[1995,10]]},"DOI":"10.1007\/bf01294130","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T03:39:08Z","timestamp":1111721948000},"page":"322-339","source":"Crossref","is-referenced-by-count":6,"title":["An efficient parallel algorithm for shortest paths in planar layered digraphs"],"prefix":"10.1007","volume":"14","author":[{"given":"S.","family":"Subramanian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Tamassia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. S.","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. Park, Notes on searching multidimensional monotone arrays,Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 496?512.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"CR2","unstructured":"N. Alon and Z. Galil, On the exponent of the all pairs shortest path problem,Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 569?575."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1137\/0219066","volume":"19","author":"A. Apostolico","year":"1990","unstructured":"A. Apostolico, M. J. Atallah, L. Larmore, and H. S. Mcfaddin, Efficient parallel algorithms for string editing and related problems,SIAM Journal on Computing,19 (1990), 968?988.","journal-title":"SIAM Journal on Computing"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"M. J. Atallah, A faster parallel algorithm for a matrix searching problem,Proc. 2nd Scandinavian Workshop on Algorithm Theory, 1990, pp. 193?200.","DOI":"10.1007\/3-540-52846-6_89"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"R. Bellman, On a routing problem,Quarterly Journal of Applied Mathematics,16 (1958), 87?90.","journal-title":"Quarterly Journal of Applied Mathematics"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"E. Cohen, Efficient parallel shortest-paths in digraphs with a separator decomposition,Proc. 5th Annual Symposium on Parallel Algorithms and Architectures, 1993, pp. 57?67.","DOI":"10.1145\/165231.165240"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, Optimal parallel algorithms for expression tree evaluation and list ranking,Proc. Third Aegean Workshop on Computing, 1988, pp. 91?100.","DOI":"10.1007\/BFb0040377"},{"key":"CR8","unstructured":"A. L. Deicher and S. R. Kosaraju, An NC algorithm for evaluating monotone planar circuits, Manuscript."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"G. Di Battista and E. Nardelli, An algorithm for testing planarity of hierarchical graphs,Proc. Workshop WG86, Bernierd, June 1986 (1987), pp. 277?289.","DOI":"10.1007\/3-540-17218-1_65"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra, A note on two problems in connexion with graphs,Numerische Mathematik,1 (1959), 269?271.","journal-title":"Numerische Mathematik"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G. N. Frederickson","year":"1987","unstructured":"G. N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications,SIAM Journal on Computing,16 (1987), 1004?1022.","journal-title":"SIAM Journal on Computing"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms,Journal of the Association for Computing Machinery,34 (1987), 596?615.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"H. Gazit and G. L. Miller, A parallel algorithm for finding a separator in planar graphs,Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 238?248.","DOI":"10.1109\/SFCS.1987.3"},{"key":"CR14","volume-title":"Graphs and Algorithms","author":"M. Gondran","year":"1984","unstructured":"M. Gondran and M. Minoux, inGraphs and Algorithms, Wiley Interscience, New York, 1984."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Y. Han, V. Pan, and J. H. Reif, Efficient parallel algorithms for computing all pair shortest paths in directed graphs,Proc. Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 353?362.","DOI":"10.1145\/140901.141913"},{"key":"CR16","first-page":"871","volume-title":"Handbook of Theoretical Computer Science","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran, A survey of parallel algorithms for shared memory machines, inHandbook of Theoretical Computer Science (J. van Leeuwen, ed.), North-Holland, Amsterdam, 1990, pp. 871?941."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"P. N. Klein and S. Subramanian, A linear-processor polylog-time algorithm for shortest-paths in planar graphsProc. 1993 IEEE Symposium on Foundations of Computer Science, 1993, pp. 259?270","DOI":"10.1109\/SFCS.1993.366861"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G. L. Miller","year":"1986","unstructured":"G. L. Miller, Finding small simple cycle separators for 2-connected planar graphs,Journal of Computer and System Sciences,32 (1986), 265?279.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"G. L. Miller and W. Thurston, Separators in two and three dimensions,Proc. 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 300?309.","DOI":"10.1145\/100216.100255"},{"key":"CR20","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"E. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976."},{"key":"CR21","unstructured":"A. Lempel, S. Even, and I. Cederbaum, An algorithm for planitary testing of graphs,Theory of Graphs, Proc. Internat. Symposium, 1966, pp. 215?232."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem,SIAM Journal on Computing,9 (1980), 615?627.","journal-title":"SIAM Journal on Computing"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1016\/0022-0000(89)90013-5","volume":"38","author":"V. Pan","year":"1989","unstructured":"V. Pan and J. H. Reif, Fast and efficient solution of path algebra problems,Journal of Computer and System Sciences,38 (1989), 494?510.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(91)90013-8","volume":"40","author":"V. Pan","year":"1991","unstructured":"V. Pan and J. H. Reif, The parallel computation of minimum cost paths in graphs by stream contraction,Information Processing Letters,40 (1991), 79?83.","journal-title":"Information Processing Letters"},{"key":"CR25","unstructured":"G. Shannon and F. Wan, Subdividing Planar Graphs in Parallel, Technical Report, Department of Computer Science, Indiana Universty, 1991."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/BF01840401","volume":"5","author":"R. Tamassia","year":"1990","unstructured":"R. Tamassia and F. P. Preparata, Dynamic maintenance of planar digraphs, with applications,Algorithmica,5 (1990), 509?527.","journal-title":"Algorithmica"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1137\/0220045","volume":"20","author":"R. Tamassia","year":"1990","unstructured":"R. Tamassia and J. S. Vitter, Parallel transitive closure and point location in planar structures,SIAM Journal on Computing,20 (1990), 708?725.","journal-title":"SIAM Journal on Computing"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. Valdes, R. E. Tarjan, and E. L. Lawler, The recognition of series parallel digraphs,SIAM Journal on Computing,11 (1982), 298?313.","journal-title":"SIAM Journal on Computing"},{"key":"CR29","first-page":"3","volume":"14","author":"S. Whitesides","year":"1969","unstructured":"S. Whitesides, Forms of hierarchy: a selected bibliography,General Systems,14 (1969), 3?15.","journal-title":"General Systems"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294130.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01294130\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01294130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T19:42:19Z","timestamp":1735414939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01294130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["BF01294130"],"URL":"https:\/\/doi.org\/10.1007\/bf01294130","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}