{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:42Z","timestamp":1725663282812},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540528463"},{"type":"electronic","value":"9783540471646"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52846-6_98","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:43:44Z","timestamp":1330206224000},"page":"288-300","source":"Crossref","is-referenced-by-count":2,"title":["Efficient parallel algorithms for shortest paths in planar graphs"],"prefix":"10.1007","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","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"26_CR1","doi-asserted-by":"publisher","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, T. Przytycka, \u201cA Simple Parallel Tree Contraction Algorithms\u201d, J. of Algorithms, 10(1989), pp.287\u2013302.","journal-title":"J. of Algorithms"},{"issue":"1","key":"26_CR2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1137\/0217004","volume":"17","author":"D. Beinstock","year":"1988","unstructured":"D. Beinstock, C.L. Monma, \u201cOn the complexity of covering faces by vertices in a planar graph\u201d, SIAM J. Comp., Vol.17, No.1, Feb. 1988, pp.53\u201376.","journal-title":"SIAM J. Comp."},{"issue":"1","key":"26_CR3","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole, U. Vishkin, \u201cDeterministic Coin Tossing with Applications to Optimal Parallel List Ranking\u201d, Inform. and Control, Vol.70, No.1, pp.32\u201353, July 1986.","journal-title":"Inform. and Control"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"E.W. Dijkstra, \u201cA note on two problems in connexion with graphs\u201d, Numerische Mathematik, 1(1959), pp.275\u2013323.","journal-title":"Numerische Mathematik"},{"issue":"4","key":"26_CR5","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1137\/0210049","volume":"10","author":"E. Dekel","year":"1981","unstructured":"E. Dekel, D. Nassimi, S. Sahni, \u201cParallel Matrix and Graph Algorithms\u201d, SIAM J. Comp., Vol.10, No.4, Nov.1981, pp.657\u2013675.","journal-title":"SIAM J. Comp."},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01762113","volume":"3","author":"G.N. Frederickson","year":"1988","unstructured":"G.N. Frederickson, R. Janardan, \u201cDesigning Networks with Compact Routing Tables\u201d, Algorithmica, 3(1988), pp.171\u2013190.","journal-title":"Algorithmica"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R.W. Floyd","year":"1962","unstructured":"R.W. Floyd, Algorithm 97: shortest path, Comm. ACM, 5(1962), pp.345.","journal-title":"Comm. ACM"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M.L. Fredman","year":"1976","unstructured":"M.L. Fredman, \u201cNew bounds on the complexity of the shortest path problem\u201d, SIAM J. Comp., 5(1976), pp.83\u201389.","journal-title":"SIAM J. Comp."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cA new approach to all pairs shortest paths in planar graphs\u201d, Proc. 19th ACM STOC, New York City, May 1987, pp.19\u201328.","DOI":"10.1145\/28395.28398"},{"key":"26_CR10","volume-title":"\u201cPlanar Graph Decomposition and All Pairs Shortest Paths\u201d, TR-89-015","author":"G.N. Frederickson","year":"1989","unstructured":"G.N. Frederickson, \u201cPlanar Graph Decomposition and All Pairs Shortest Paths\u201d, TR-89-015, ICSI, Berkeley, March 1989."},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cUsing Cellular Graph Embeddings in Solving All Pairs Shortest Path Problems\u201d, Proc. 30th Annual IEEE Symp. on FOCS, 1989, pp.448\u2013453; also CSD-TR-897, Purdue University, August 1989.","DOI":"10.1109\/SFCS.1989.63517"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"M.L. Fredman, R.E. Tarjan, \u201cFibonacci heaps and their uses in improved network optimization algorithms\u201d, JACM, 34(1987), pp.596\u2013615.","journal-title":"JACM"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"A. Goldberg, S. Plotkin, G. Shannon, \u201cParallel Symmetry-Breaking in Sparse Graphs\u201d, Proc. of the 19th ACM STOC, 1987, pp.315\u2013324.","DOI":"10.1145\/28395.28429"},{"key":"26_CR14","unstructured":"T. Hagerup, \u201cOptimal Parallel Algorithms for Planar Graphs\u201d, Inform. and Computation, to appear."},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"P. Klein, J.H. Reif, \u201cAn Efficient Parallel Algorithm for Planarity\u201d, Proc. 27th Annual IEEE Symp. on FOCS, 1986, pp.465\u2013477.","DOI":"10.1109\/SFCS.1986.6"},{"key":"26_CR16","volume-title":"\u201cA Survey of Parallel Algorithms for Shared-Memory Machines\u201d, Rep.No. UCB\/CSD 88\/804","author":"R.M. Karp","year":"1989","unstructured":"R.M. Karp, V. Ramachandran, \u201cA Survey of Parallel Algorithms for Shared-Memory Machines\u201d, Rep.No. UCB\/CSD 88\/804, University of California, Berkeley, 1989."},{"key":"26_CR17","volume-title":"\u201cEfficient Parallel Algorithms for Shortest Paths in Planar Graphs\u201d, TR-90.01.02","author":"G. Pantziou","year":"1990","unstructured":"G. Pantziou, P. Spirakis, C. Zaroligis, \u201cEfficient Parallel Algorithms for Shortest Paths in Planar Graphs\u201d, TR-90.01.02, Computer Technology Institute, Patras, January 1990."},{"key":"26_CR18","volume-title":"\u201cOptimal Parallel Algorithms for Sparse Graphs\u201d, TR-90.04.08","author":"G. Pantziou","year":"1990","unstructured":"G. Pantziou, P. Spirakis, C. Zaroliagis, \u201cOptimal Parallel Algorithms for Sparse Graphs\u201d, TR-90.04.08, Computer Technology Institute, Patras, April 1990 (revised version)."},{"key":"26_CR19","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S. Warshall","year":"1962","unstructured":"S. Warshall, \u201cA theorem on Boolean matrices\u201d, JACM, 9(1962), pp.11\u201312.","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","SWAT 90"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52846-6_98.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:09:34Z","timestamp":1619572174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52846-6_98"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540528463","9783540471646"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-52846-6_98","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}