{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:02:13Z","timestamp":1761807733102,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631651"},{"type":"electronic","value":"9783540691945"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63165-8_195","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:11:16Z","timestamp":1330297876000},"page":"390-400","source":"Crossref","is-referenced-by-count":23,"title":["Efficient parallel graph algorithms for coarse grained multicomputers and BSP"],"prefix":"10.1007","author":[{"given":"E.","family":"C\u00e1ceres","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Dehne","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Ferreira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Flocchini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Rieping","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Roncato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Santoro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. W.","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"37_CR1","unstructured":"S.G. Akl, Parallel Computation, Prentice Hall, 1997."},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"R.J. Anderson, and L. Snyder, \u201cA Comparison of Shared and Nonshared Memory Models of Computation,\u201d in Proc. of the IEEE, 79(4), pp. 480\u2013487.","DOI":"10.1109\/5.92042"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"A. B\u00e4umker and W. Dittrich, \u201cParallel Algorithms for Image Processing: Practical Algorithms with Experiments,\u201d International Parallel Processing Symposium, IEEE Computer Society Press, 1996, pp. 429\u2013433.","DOI":"10.1109\/IPPS.1996.508091"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"G.E. Blelloch, C.E. Leiserson, B.M. Maggs, C.G. Plaxton, \u201cA Comparison of Sorting Algorithms for the Connection Machine CM-2.,\u201d in Proc. ACM Symp. on Parallel Algorithms and Architectures, 1991, pp. 3\u201316.","DOI":"10.1145\/113379.113380"},{"key":"37_CR5","unstructured":"E. C\u00e1ceres, F. Dehne, A. Ferreira, P. Flocchini, I. Rieping, A. Roncato, N. Santoro, and S.W. Song, \u201cEfficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP,\u201d, on-line Postscript at http:\/\/www.scs.carleton.ca\/scs\/faculty\/dehne.html."},{"issue":"4","key":"37_CR6","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, \u201cParallel merge sort,\u201d SIAM J. Comput., 17(4), 1988, pp. 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, \u201cApproximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time\u201d, SIAM Journal of Computing, Vol. 17, No. 1, 1988.","DOI":"10.1137\/0217009"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"F. Dehne, A. Fabri, and A. Rau-Chaplin, \u201cScalable Parallel Geometric Algorithms for Coarse Grained Multicomputers,\u201d in Proc. ACM 9th Annual Computational Geometry, pages 298\u2013307, 1993.","DOI":"10.1145\/160985.161154"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"F. Dehne, A. Fabri, and C. Kenyon, \u201cScalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time,\u201d in Proc. 6th IEEE Symposium on Parallel and Distributed Processing, pages 586\u2013593, 1994.","DOI":"10.1109\/SPDP.1994.346119"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"F. Dehne, X. Deng, P. Dymond, A. Fabri, and A. A. Kokhar, \u201cA randomized parallel 3D convex hull algorithm for coarse grained multicomputers,\u201d in Proc. ACM Symposium on Parallel Algorithms and Architectures (SPAA'95), pp. 27\u201333, 1995.","DOI":"10.1145\/215399.215410"},{"key":"37_CR11","unstructured":"F.Dehne, S.W. Song, \u201cRandomized parallel list ranking for distributed memory multiprocessors,\u201d in Proc. Second Asian Computing Science Conference, ASIAN'96, Singapore, Dec. 1996, Springer Lecture Notes in Computer Science 1179, pp. 1\u201310."},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"X. Deng, \u201cA Convex Hull Algorithm for Coarse Grained Multiprocessors,\u201d in Proc. 5th International Symposium on Algorithms and Computation, 1994.","DOI":"10.1007\/3-540-58325-4_232"},{"key":"37_CR13","unstructured":"X. Deng and P. Dymond, \u201cEfficient Routing and Message Bounds for Optimal Parallel Algorithms,\u201d in Proc. Int. Parallel Proc. Symp., 1995."},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"X. Deng and N. Gu, \u201cGood Programming Style on Multiprocessors,\u201d in Proc. IEEE Symposium on Parallel and Distributed Processing, 1994, pp. 538\u2013543.","DOI":"10.1109\/SPDP.1994.346125"},{"key":"37_CR15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"G.A. Dirac. \u201cOn rigid circuit graphs\u201d. Abh. Math. Sem. Univ. Hamburg 25, 1961, pp. 71\u201376.","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"37_CR16","first-page":"561","volume-title":"Scalable 2d convex hull and triangulation algorithms for coarse-grained multicomputers","author":"A. Ferreira","year":"1995","unstructured":"A. Ferreira, A. Rau-Chaplin, and S. Ubeda, \u201cScalable 2d convex hull and triangulation algorithms for coarse-grained multicomputers,\u201d in Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing \u2014 SPDP'95, pages 561\u2013569, San Antonio (USA), October 1995. IEEE Press."},{"key":"37_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-55706-7_1","volume":"621","author":"A.V. Gerbessiotis","year":"1992","unstructured":"A.V. Gerbessiotis and L.G. Valiant, \u201cDirect Bulk-Synchronous Parallel Algorithms,\u201d in Proc. 3rd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 621, 1992, pp. 1\u201318.","journal-title":"Proc. 3rd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science"},{"key":"37_CR18","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, \u201cCommunication efficient parallel sorting,\u201d ACM Symposium on Theory of Computing (STOC), 1996.","DOI":"10.1145\/237814.237870"},{"key":"37_CR19","unstructured":"Ja'Ja', An Introduction to Parallel Algorithms, Addison Wesley, 1992."},{"key":"37_CR20","doi-asserted-by":"crossref","unstructured":"P. Klein. \u201cEfficient Parallel Algorithms for Chordal Graphs\u201d. Proc. 29th Symp. Found. of Comp. Sci., FOCS 1989, pp. 150\u2013161.","DOI":"10.1109\/SFCS.1988.21933"},{"key":"37_CR21","unstructured":"P. Klein. \u201cParallel Algorithms for Chordal Graphs\u201d. In Synthesis of parallel algorithms, J. H. Reif (editor). Morgan Kaufmann Publishers, 1993, pp. 341\u2013407."},{"key":"37_CR22","doi-asserted-by":"crossref","unstructured":"Hui Li, and K. C. Sevcik, \u201cParallel Sorting by Overpartitioning,\u201d in Proc. ACM Symp. on Parallel Algorithms and Architectures, 1994, pp. 46\u201356.","DOI":"10.1145\/181014.192329"},{"key":"37_CR23","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(86)90153-2","volume":"47","author":"Y. Maon","year":"1986","unstructured":"Y. Maon, B. Schieber, U. Vishkin. \u201cParallel ear decomposition search (EDS) and st-numbering in graphs\u201d. Theoretical Computer Science, vol. 47, 1986, pp. 277\u2013298.","journal-title":"Theoretical Computer Science"},{"key":"37_CR24","doi-asserted-by":"crossref","unstructured":"G.L. Miller, J.H. Reif, \u201cParallel tree contraction and its application,\u201d IEEE Symp. on Foundations of Computer Science, 1985, pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"37_CR25","volume-title":"Efficient parallel ear decomposition with applications","author":"G. L. Miller","year":"1986","unstructured":"G. L. Miller, V. Ramachandran. \u201cEfficient parallel ear decomposition with applications\u201d, manuscript, MSRI, Berkeley, January 1986."},{"key":"37_CR26","unstructured":"V. Ramachandran. \u201cParallel open ear decomposition with applications to graph biconnectivity and triconnectivity\u201d, in [28], pp. 276\u2013340."},{"key":"37_CR27","doi-asserted-by":"crossref","unstructured":"M. Reid-Miller, \u201cList ranking and list scan on the Cray C-90,\u201d in Proc. ACM Symp. on Parallel Algorithms and Architectures, 1994, pp. 104\u2013113.","DOI":"10.1145\/181014.181049"},{"key":"37_CR28","unstructured":"J. H. Reif (editor), Synthesis of parallel algorithms, Morgan Kaufmann Publishers, 1993."},{"key":"37_CR29","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"D.J. Rose, R.E. Tarjan, and G.S. Lueker. \u201cAlgorithmic Aspects of Vertex Elimination on Graphs\u201d. SIAM J. Comp. 5, 1976, pp. 266\u2013283.","journal-title":"SIAM J. Comp."},{"issue":"1","key":"37_CR30","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloch","year":"1983","unstructured":"Y. Shiloch, U. Vishkin, \u201cAn O(log n) parallel connectivity algorithm,\u201d Journal of Algorithms, 3(1), pp. 57\u201367, 1983.","journal-title":"Journal of Algorithms"},{"key":"37_CR31","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1146\/annurev.cs.01.060186.001445","volume":"1","author":"L. Snyder","year":"1986","unstructured":"L. Snyder, \u201cType architectures, shared memory and the corollary of modest potential,\u201d Annu. Rev. Comput. Sci. 1, 1986, pp. 289\u2013317.","journal-title":"Annu. Rev. Comput. Sci."},{"issue":"4","key":"37_CR32","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan, U. Vishkin, \u201cAn efficient parallel biconnectivity algorithm,\u201d SIAM J. Comput., 14(4), 1985, pp. 862\u2013874.","journal-title":"SIAM J. Comput."},{"key":"37_CR33","doi-asserted-by":"crossref","unstructured":"L. Valiant, \u201cA bridging model for parallel computation,\u201d Communications of the ACM, Vol. 33, No. 8, August 1990.","DOI":"10.1145\/79173.79181"},{"key":"37_CR34","doi-asserted-by":"crossref","unstructured":"L.G. Valiant et al., \u201cGeneral Purpose Parallel Architectures,\u201d Handbook of Theoretical Computer Science, Edited by J. van Leeuwen, MIT Press\/Elsevier, 1990, pp.943\u2013972.","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"37_CR35","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H. Whitney","year":"1932","unstructured":"H. Whitney. \u201cNon-separable and planar graphs\u201d. Trans. Amer. Math. Soc. 34, 1932, pp. 339\u2013362.","journal-title":"Trans. Amer. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63165-8_195.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:38:41Z","timestamp":1742600321000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63165-8_195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631651","9783540691945"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-63165-8_195","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}