{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:56Z","timestamp":1759637576889},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01994878","type":"journal-article","created":{"date-parts":[[2005,8,4]],"date-time":"2005-08-04T20:22:09Z","timestamp":1123186929000},"page":"215-236","source":"Crossref","is-referenced-by-count":5,"title":["Efficient parallel algorithms for shortest paths in planar digraphs"],"prefix":"10.1007","volume":"32","author":[{"given":"Grammati E.","family":"Pantziou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos D.","family":"Zaroliagis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01994878_CR1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. Kirkpatrick and T. Przytycka,A simple parallel tree contraction algorithm, J. of Algorithms, 10 (1989), pp. 287\u2013302.","journal-title":"J. of Algorithms"},{"issue":"1","key":"BF01994878_CR2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1137\/0217004","volume":"17","author":"D. Beinstock","year":"1988","unstructured":"D. Beinstock and C. Monma,On the complexity of covering faces by vertices in a planar graph, SIAM J. Comp., Vol. 17, No. 1, Feb. 1988, pp. 53\u201376.","journal-title":"SIAM J. Comp."},{"key":"BF01994878_CR3","doi-asserted-by":"crossref","unstructured":"B. Berger, J. Rompel and P. Shor,Efficient NC-algorithms for set cover with applications to learning and geometry, Proc. 30th IEEE Symp. on FOCS, 1989, pp. 54\u201359.","DOI":"10.1109\/SFCS.1989.63455"},{"issue":"1","key":"BF01994878_CR4","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin,Appropriate parallel scheduling. Part I:The basic technique with applications to optimal parallel list ranking in logarithmic time, SIAM J. Comp., Vol. 17, No. 1, February 1989, pp. 128\u2013142.","journal-title":"SIAM J. Comp."},{"key":"BF01994878_CR5","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra,A note on two problems in connection with graphs, Numerische Mathematik, 1 (1959), pp. 275\u2013323.","journal-title":"Numerische Mathematik"},{"issue":"4","key":"BF01994878_CR6","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1137\/0210049","volume":"10","author":"E. Dekel","year":"1981","unstructured":"E. Dekel, D. Nassimi and S. Sahni,Parallel matrix and graph algorithms, SIAM J. Comp., Vol. 10, No. 4, Nov. 1981, pp. 657\u2013675.","journal-title":"SIAM J. Comp."},{"key":"BF01994878_CR7","first-page":"327","volume":"510","author":"H. Djidjev","year":"1991","unstructured":"H. Djidjev, G. Pantziou and C. Zaroliagis,Computing shortest paths and distances in planar graphs, in Proc. 18th ICALP, 1991, LNCS, Vol. 510, pp. 327\u2013339.","journal-title":"Proc. 18th ICALP"},{"key":"BF01994878_CR8","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R. Floyd","year":"1962","unstructured":"R. Floyd,Algorithm 97: shortest path, Comm. ACM 5 (1962), pp. 345.","journal-title":"Comm. ACM"},{"key":"BF01994878_CR9","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01762113","volume":"3","author":"G. N. Frederickson","year":"1988","unstructured":"G. N. Frederickson and R. Janardan,Designing networks with compact routing tables, Algorithmica, 3 (1988), pp. 171\u2013190.","journal-title":"Algorithmica"},{"key":"BF01994878_CR10","doi-asserted-by":"crossref","unstructured":"G. N. Frederickson,A new approach to all pairs shortest paths in planar graphs, Proc. 19th ACM STOC, New York City, May 1987, pp. 19\u201328.","DOI":"10.1145\/28395.28398"},{"issue":"1","key":"BF01994878_CR11","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1145\/102782.102788","volume":"38","author":"G. N. Frederickson","year":"1991","unstructured":"G. N. Frederickson,Planar graph decomposition and all pairs shortest paths, JACM, Vol. 38, No. 1, January 1991, pp. 162\u2013204; also TR-89-015, ICSI, Berkely, March 1989.","journal-title":"JACM"},{"key":"BF01994878_CR12","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M. Fredman","year":"1976","unstructured":"M. Fredman,New bounds on the complexity of the shortest path problem, SIAM J. Comp., 5 (1976), pp. 83\u201389.","journal-title":"SIAM J. Comp."},{"key":"BF01994878_CR13","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"M. Fredman and R. Tarjan,Fibonacci heaps and their uses in improved network optimization algorithms, JACM, 34 (1987), pp. 596\u2013615.","journal-title":"JACM"},{"key":"BF01994878_CR14","doi-asserted-by":"crossref","unstructured":"H. Gazit and G. Miller,A parallel algorithm for finding a separator in planar graphs in Proc. of the 28th IEEE Symp. FOCS, 1987, pp. 238\u2013248.","DOI":"10.1109\/SFCS.1987.3"},{"key":"BF01994878_CR15","doi-asserted-by":"crossref","unstructured":"A. Goldberg, S. Plotkin and G. Shannon,Parallel symmetry-breaking in sparse graphs, Proc. of the 19th ACM STOC, 1987, pp. 315\u2013324.","DOI":"10.1145\/28395.28429"},{"key":"BF01994878_CR16","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0890-5401(90)90034-F","volume":"84","author":"T. Hagerup","year":"1990","unstructured":"T. Hagerup,Optimal parallel algorithms for planar graphs, Inform. and Computation, Vol. 84, 1990, pp. 71\u201396.","journal-title":"Inform. and Computation"},{"key":"BF01994878_CR17","unstructured":"T. Hagerup, G. Pantziou and C. Zaroliagis,Efficient sequential and parallel algorithms for planar digraph problems, CTI Tech. Rep. TR-91.09.22, Sept. 1991. Submitted."},{"key":"BF01994878_CR18","doi-asserted-by":"crossref","unstructured":"P. Klein and J. Reif,An efficient parallel algorithm for planarity, Proc. 27th Annual IEEE Symp. on FOCS, 1986, pp. 465\u2013477.","DOI":"10.1109\/SFCS.1986.6"},{"key":"BF01994878_CR19","volume-title":"A survey of parallel algorithms for shared-memory machines","author":"R. Karp","year":"1989","unstructured":"R. Karp and V. Ramachandran,A survey of parallel algorithms for shared-memory machines, Rep. No. UCB\/CSD 88\/804, University of California, Berkely, 1989."},{"key":"BF01994878_CR20","doi-asserted-by":"crossref","unstructured":"A. Lingas,Efficient parallel algorithms for path problems in planar directed graphs, Proc. SIGAL '90, Tokyo, LNCS, Springer Verlag.","DOI":"10.1007\/3-540-52921-7_94"},{"key":"BF01994878_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-53832-1_27","volume":"484","author":"G. Pantziou","year":"1990","unstructured":"G. Pantziou, P. Spirakis and C. Zaroliagis,Optimal parallel algorithms for sparse graphs, in Proc. of 16th Int'l Workshop on Graph-Theoretic Concepts in Computer Science (WG90), Berlin, 19\u201322 June, 1990, LNCS Vol. 484, pp. 1\u201317, Springer-Verlag.","journal-title":"Proc. of 16th Int'l Workshop on Graph-Theoretic Concepts in Computer Science (WG90), Berlin"},{"key":"BF01994878_CR22","first-page":"288","volume":"447","author":"G. Pantziou","year":"1990","unstructured":"G. Pantziou, P. Spirakis and C. Zaroliagis,Efficient parallel algorithms for shortest paths in planar graphs, Proc. of the 2nd Scand. Workshop on Algorithm Theory (SWAT90), Bergen, Norway, 11\u201314 July, 1990, LNCS, Vol. 447, pp. 288\u2013300, Springer-Verlag.","journal-title":"Proc. of the 2nd Scand. Workshop on Algorithm Theory (SWAT90), Bergen, Norway"},{"key":"BF01994878_CR23","volume-title":"Efficient parallel algorithms for shortest paths in planar digraphs","author":"G. Pantziou","year":"1991","unstructured":"G. Pantziou, P. Spirakis and C. Zaroliagis,Efficient parallel algorithms for shortest paths in planar digraphs, TR-91.07.21, Computer Technology Institute, Patras, July 1991."},{"key":"BF01994878_CR24","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-642-95486-3_22","volume-title":"The Book of L","author":"J. Leeuwen van","year":"1986","unstructured":"J. van Leeuwen and R. Tan,Computer networks with compact routing tables, in The Book of L, G. Rozenberg and A. Salomaa (eds.), Springer-Verlag, NY (1986), pp. 259\u2013273."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994878.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01994878\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994878","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T17:37:20Z","timestamp":1586367440000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01994878"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01994878"],"URL":"https:\/\/doi.org\/10.1007\/bf01994878","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}