{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:57:30Z","timestamp":1777676250976,"version":"3.51.4"},"reference-count":16,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2005,2,1]],"date-time":"2005-02-01T00:00:00Z","timestamp":1107216000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2005,2]]},"abstract":"<jats:p>In this paper, we present CGMgraph, the first integrated library of parallel graph methods for PC clusters based on Coarse Grained Multicomputer (CGM) algorithms. CGMgraph implements parallel methods for various graph problems. Our implementations of deterministic list ranking, Euler tour, connected components, spanning forest, and bipartite graph detection are, to our knowledge, the first efficient implementations for PC clusters. Our library also includes CGMlib, a library of basic CGM tools such as sorting, prefix sum, one-to-all broadcast, all-to-one gather, h-Relation, all-to-all broadcast, array balancing, and CGM partitioning. Both libraries are available for download at http:\/\/www.scs.carleton.ca\/~cgm.<\/jats:p>\n                  <jats:p>In the experimental part of this paper, we demonstrate the performance of our methods on four different architectures: a gigabit connected high performance PC cluster, a smaller PC cluster connected via fast ethernet, a network of workstations, and a shared memory machine. Our experiments show that our library provides good parallel speedup and scalability on all four platforms. The communication overhead is, in most cases, small and does not grow significantly with an increasing number of processors. This is a very important feature of CGM algorithms which makes them very efficient in practice.<\/jats:p>","DOI":"10.1177\/1094342005051196","type":"journal-article","created":{"date-parts":[[2005,2,21]],"date-time":"2005-02-21T14:39:07Z","timestamp":1108996747000},"page":"81-97","source":"Crossref","is-referenced-by-count":33,"title":["CGMGRAPH\/CGMLIB: Implementing and Testing CGM Graph Algorithms on PC Clusters                 and Shared Memory Machines"],"prefix":"10.1177","volume":"19","author":[{"given":"Albert","family":"Chan","sequence":"first","affiliation":[{"name":"DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE FAYETTEVILLE STATE\r                        UNIVERSITY FAYETTEVILLE, NC 28301, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Dehne","sequence":"additional","affiliation":[{"name":"SCHOOL OF ICT GRIFFITH UNIVERSITY NATHAN, QLD 4111, AUSTRALIA\r                        HTTP:\/\/WWW.DEHNE.NET"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Taylor","sequence":"additional","affiliation":[{"name":"SCHOOL OF COMPUTER SCIENCE CARLETON UNIVERSITY OTTAWA, CANADA K1S 5B6"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2005,2,1]]},"reference":[{"key":"atypb1","first-page":"83","volume-title":"Proceedings of the 26th Workshop on GraphTheoretic Concepts in Computer Science (WG 2000), Lecture Notes in Computer Science Vol. 1928","author":"Caceres, E."},{"key":"atypb2","volume-title":"Technical Report TR-98-06, School of Computer Scien","author":"Chan, A.","year":"1998"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626499000499"},{"key":"atypb4","first-page":"117","volume-title":"Proceedings of the 10th European PVM\/MPI Users Group Meeting (Euro PVM\/MPI03), Lecture Notes in Computer Science Vol. 2840","author":"Chan, A."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0109-4"},{"key":"atypb6","first-page":"1","volume-title":"Asian Computer Science Conference (ASIAN \u201896), Lecture Notes in Computer Science Vol. 1179","author":"Dehne, F."},{"key":"atypb7","first-page":"298","volume-title":"ACM Symposium on Computational Geometry","author":"Dehne, F."},{"key":"atypb8","volume-title":"Proceedings of the 28th Annual ACM Symposium on Theory of Computing","author":"Goodrich, M.T."},{"key":"atypb9","volume-title":"Technical Report RR\u2013 3885, INRIA","author":"Guerin Lassous, I.","year":"2000"},{"key":"atypb10","first-page":"104","volume-title":"ACM Symposium on Parallel Algorithms and Architectures","author":"Reid-Miller, M."},{"key":"atypb11","volume-title":"Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers","author":"Reif, J.","year":"1993"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90075-X"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050131"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1508"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1177\/1094342005051521"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342005051196","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342005051196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:18:09Z","timestamp":1777450689000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342005051196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,2]]}},"alternative-id":["10.1177\/1094342005051196"],"URL":"https:\/\/doi.org\/10.1177\/1094342005051196","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,2]]}}}