{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:19Z","timestamp":1725663379353},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540529217"},{"type":"electronic","value":"9783540471776"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52921-7_94","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:49:59Z","timestamp":1330206599000},"page":"447-457","source":"Crossref","is-referenced-by-count":5,"title":["Efficient parallel algorithms for path problems in planar directed graphs"],"prefix":"10.1007","author":[{"given":"Andrezej","family":"Lingas","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"46_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, Massachusetts, 1974)."},{"doi-asserted-by":"crossref","unstructured":"R. Cole, Parallel Merge Sort, Proc. 27th Ann. Symp. on Foundations of Computer Science.","key":"46_CR2","DOI":"10.1109\/SFCS.1986.41"},{"doi-asserted-by":"crossref","unstructured":"D. Coppersmith, S. Winograd, Matrix Multiplication via Arithmetic Progressions, Proc. 28th Annual ACM Symp. on Theory of Computing, 1987, pp. 1\u20136.","key":"46_CR3","DOI":"10.1145\/28395.28396"},{"unstructured":"H. Gazit, personnal communication, 1989.","key":"46_CR4"},{"doi-asserted-by":"crossref","unstructured":"H. Gazit and G.L. Miller, A Parallel Algorithm for Finding a Separator in Planar Graphs, Proc. 28th Symp. on Foundations of Computer Science, 1987.","key":"46_CR5","DOI":"10.1109\/SFCS.1987.3"},{"unstructured":"R.M. Karp and V. Ramachandran, A Survey of Parallel Algorithms for Shared-Memory Machines, Technical Report UCB-CSD 88\u2013408, Computer Science Division, EECS, University of California at Berkeley, 1988. To appear in the Handbook of Theoretical Computer Science, North-Holland.","key":"46_CR6"},{"doi-asserted-by":"crossref","unstructured":"M.Y. Kao, P.N. Klein, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, to appear in Proc. 22nd Annual ACM Symp. on Theory of Computing, 1990.","key":"46_CR7","DOI":"10.1145\/100216.100237"},{"doi-asserted-by":"crossref","unstructured":"P.N. Klein, J.H. Reif, An Efficient Parallel Algorithm for Planarity, Proc. 27th Symp. on Foundations on Computer Science, 1986.","key":"46_CR8","DOI":"10.1109\/SFCS.1986.6"},{"doi-asserted-by":"crossref","unstructured":"M.Y. Kao, G. Shannon, Local Reorientation, Global Order, and Planar Topology, Proc. 21st Annual ACM Symp. on Theory of Computing, Seattle, 1989.","key":"46_CR9","DOI":"10.1145\/73007.73034"},{"key":"46_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton and R.E. Tarjan, A Separator Theorem for Planar Graphs, SIAM J. Appl. Math. 36 (1979), pp. 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness Springer Verlag, 1984, pp. 155\u2013158.","key":"46_CR11","DOI":"10.1007\/978-3-642-69897-2_3"},{"unstructured":"J. Reif, personnal communication, 1989.","key":"46_CR12"},{"key":"46_CR13","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0020-0190(80)90128-3","volume":"11","author":"F. Romani","year":"1980","unstructured":"F. Romani, Shortest-path problem is not harder than matrix multiplication, Information Processing Letters, 11(1980), pp. 134\u2013136.","journal-title":"Information Processing Letters"},{"key":"46_CR14","series-title":"Technical Report","volume-title":"Extension of the Parallel Nested Dissection Algorithm to the Path Algebra Problems","author":"V.P. Pan","year":"1985","unstructured":"V.P. Pan and J. Reif, Extension of the Parallel Nested Dissection Algorithm to the Path Algebra Problems, Technical Report 85-9, Comput. Sci. Dept., SUNYA, Albany, NY, 1985."},{"key":"46_CR15","first-page":"494","volume":"38","author":"V.P. Pan","year":"1989","unstructured":"V.P. Pan and J. Reif, Fast and Efficient Solution of Path Algebra Problems, JCSS 38 (1989), pp. 494\u2013510.","journal-title":"JCSS"},{"doi-asserted-by":"crossref","unstructured":"Y. Shiloach and U. Vishkin, An O(log n) Parallel Connectivity Algorithm, J. Algorithms 3, 1, 57\u201367.","key":"46_CR16","DOI":"10.1016\/0196-6774(82)90008-6"}],"container-title":["Lecture Notes in Computer Science","Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52921-7_94.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:56Z","timestamp":1605648356000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52921-7_94"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540529217","9783540471776"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-52921-7_94","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}