{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T04:43:26Z","timestamp":1725943406331},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540747413"},{"type":"electronic","value":"9783540747420"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74742-0_15","type":"book-chapter","created":{"date-parts":[[2007,8,21]],"date-time":"2007-08-21T11:03:30Z","timestamp":1187694210000},"page":"137-147","source":"Crossref","is-referenced-by-count":7,"title":["Techniques for Designing Efficient Parallel Graph Algorithms for SMPs and Multicore Processors"],"prefix":"10.1007","author":[{"given":"Guojing","family":"Cong","sequence":"first","affiliation":[]},{"given":"David A.","family":"Bader","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","volume-title":"Handbook of Parallel Computing: Models, Algorithms, and Applications","author":"D.A. Bader","year":"2007","unstructured":"Bader, D.A., Cong, G.: Efficient parallel algorithms for multi-core and multiprocessors. In: Rajasekaran, S., Reif, J. (eds.) Handbook of Parallel Computing: Models, Algorithms, and Applications, CRC press, Boca Raton, USA (2007)"},{"key":"15_CR2","volume-title":"Handbook of Parallel Computing: Models, Algorithms, and Applications","author":"D.A. Bader","year":"2007","unstructured":"Bader, D.A., Cong, G., Madduri, K.: Design of multithreaded algorithms for combinatorial problems. In: Rajasekaran, S., Reif, J. (eds.) Handbook of Parallel Computing: Models, Algorithms, and Applications, CRC press, Boca Raton, USA (2007)"},{"key":"15_CR3","unstructured":"Bader, D.A., Cong, G.: A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs). In: IPDPS 2004. Proceedings of the 18th International Parallel and Distributed Processing Symposium, Santa Fe, New Mexico (2004)"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Cong, G.: Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. In: IPDPS 2004. Proc. 18th Int\u2019l Parallel and Distributed Processing Symp., Santa Fe, New Mexico (2004)","DOI":"10.1109\/IPDPS.2004.1302953"},{"key":"15_CR5","unstructured":"Cong, G., Bader, D.: An experimental study of parallel biconnected components algorithms on symmetric multiprocessors (SMPs). In: IPDPS 2005. Proceedings of the 19th International Parallel and Distributed Processing Symposium, Denver, Colorado (2005)"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Greiner, J.: A comparison of data-parallel algorithms for connected components. In: SPAA-94. Proc. 6th Ann. Symp. Parallel Algorithms and Architectures, Cape May, NJ, pp. 16\u201325 (1994)","DOI":"10.1145\/181014.181021"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Hsu, T.S., Ramachandran, V., Dean, N.: Parallel implementation of algorithms for finding connected components in graphs. In: Bhatt, S.N. (ed.) Parallel Algorithms: 3rd DIMACS Implementation Challenge, October 17-19, 1994. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a030, pp. 23\u201341 (1997)","DOI":"10.1090\/dimacs\/030\/02"},{"key":"15_CR8","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"1","volume-title":"Parallel Algorithms: 3rd DIMACS Implementation Challenge","author":"A. Krishnamurthy","year":"1997","unstructured":"Krishnamurthy, A., Lumetta, S.S., Culler, D.E., Yelick, K.: Connected components on distributed memory machines. In: Bhatt, S.N. (ed.) Parallel Algorithms: 3rd DIMACS Implementation Challenge, October 17-19, 1994. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a030, pp. 1\u201321. American Mathematical Society, Providence, RI (1997)"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Goddard, S., Kumar, S., Prins, J.: Connected components algorithms for mesh-connected parallel computers. In: Bhatt, S.N. (ed.) Parallel Algorithms: 3rd DIMACS Implementation Challenge, October 17-19, 1994. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a030, pp. 43\u201358 (1997)","DOI":"10.1090\/dimacs\/030\/03"},{"key":"15_CR10","unstructured":"Chung, S., Condon, A.: Parallel implementation of Boruvka\u2019s minimum spanning tree algorithm. In: IPPS 1996. Proc. 10th Int\u2019l Parallel Processing Symp., pp. 302\u2013315 (1996)"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Dehne, F., G\u00f6tz, S.: Practical parallel algorithms for minimum spanning trees. In: Workshop on Advances in Parallel and Distributed Systems, West Lafayette, IN, pp. 366\u2013371 (1998)","DOI":"10.1109\/RELDIS.1998.740525"},{"key":"15_CR12","first-page":"525","volume-title":"Proc. 5th Int\u2019l Parallel Processing Symp.","author":"J. Woo","year":"1991","unstructured":"Woo, J., Sahni, S.: Load balancing on a hypercube. In: Proc. 5th Int\u2019l Parallel Processing Symp., Anaheim, CA, pp. 525\u2013530. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF01840376","volume":"5","author":"C. Kruskal","year":"1990","unstructured":"Kruskal, C., Rudolph, L., Snir, M.: Efficient parallel algorithms for graph problems. Algorithmica\u00a05, 43\u201364 (1990)","journal-title":"Algorithmica"},{"key":"15_CR14","first-page":"1","volume-title":"4th Symp. Principles and Practice of Parallel Programming, ACM SIGPLAN","author":"D.E. Culler","year":"1993","unstructured":"Culler, D.E., Karp, R.M., Patterson, D.A., Sahay, A., Schauser, K.E., Santos, E., Subramonian, R., von Eicken, T.: LogP: Towards a realistic model of parallel computation. In: 4th Symp. Principles and Practice of Parallel Programming, ACM SIGPLAN, pp. 1\u201312. ACM Press, New York (1993)"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L.G. Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM\u00a033, 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"key":"15_CR16","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison-Wesley Publishing Company, New York (1992)"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Shiloach, Y., Vishkin, U.: An O(logn) parallel connectivity algorithm. J. Algs.\u00a03, 57\u201367 (1982)","journal-title":"J. Algs."},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. Tarjan","year":"1985","unstructured":"Tarjan, R., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Computing\u00a014, 862\u2013874 (1985)","journal-title":"SIAM J. Computing"},{"key":"15_CR19","first-page":"268","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing","author":"L. Arge","year":"2002","unstructured":"Arge, L., Bender, M., Demaine, E., Holland-Minkley, B., Munro, J.: Cache-oblivious priority queue and graph algorithm applications. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Canada, pp. 268\u2013276. ACM Press, New York (2002)"},{"key":"15_CR20","first-page":"399","volume-title":"FOCS-00","author":"M. Bender","year":"2000","unstructured":"Bender, M., Demaine, E., Farach-Colton, M.: Cache-oblivious search trees. In: FOCS-00. Proc. 41st Ann. IEEE Symp. Foundations of Computer Science, Redondo Beach, CA, pp. 399\u2013409. IEEE Press, Los Alamitos (2000)"},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-48518-X_3","volume-title":"Algorithm Engineering and Experimentation","author":"D.R. Helman","year":"1999","unstructured":"Helman, D.R., J\u00e1J\u00e1, J.: Designing practical efficient algorithms for symmetric multiprocessors. In: Goodrich, M.T., McGeoch, C.C. (eds.) ALENEX 1999. LNCS, vol.\u00a01619, pp. 37\u201356. Springer, Heidelberg (1999)"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Park, J., Penner, M., Prasanna, V.: Optimizing graph algorithms for improved cache performance. In: IPDPS 2002. Proc. Int\u2019l Parallel and Distributed Processing Symp., Fort Lauderdale, FL (2002)","DOI":"10.1109\/IPDPS.2002.1015509"},{"key":"15_CR23","unstructured":"Chiang, Y.J., Goodrich, M., Grove, E., Tamassia, R., Vengroff, D., Vitter, J.: External-memory graph algorithms. In: Proceedings of the 1995 Symposium on Discrete Algorithms, pp. 139\u2013149 (1995)"}],"container-title":["Lecture Notes in Computer Science","Parallel and Distributed Processing and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74742-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T09:32:19Z","timestamp":1556789539000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74742-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540747413","9783540747420"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74742-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}