{"id":13010,"date":"2021-12-02T20:45:32","date_gmt":"2021-12-03T01:45:32","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13010"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-99-08-coarse-grained-parallel-algorithms-for-detecting-convex-bipartite-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1999\/tr-99-08-coarse-grained-parallel-algorithms-for-detecting-convex-bipartite-graphs\/","title":{"rendered":"TR-99-08: Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-99-08: Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1999\/\">Technical Report<\/a> TR-99-08<br>\nNovember 1999<\/p>\n\n\n\n<h2 id=\"coarse-grained-parallel-algorithms-for-detecting-convex-bipartite-graphs\" class=\"wp-block-heading\">Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">E. Caceres, A. Chan, Frank Dehne, G. Prencipe<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<p>Abstract In this paper, we present parallel algorithms for the coarse grained multicomputer (CGM) and bulk synchronous parallel computer (BSP) for solving two well known graph problems: (1) determining whether a graph G is bipartite, and (2) determining whether a bipartite graph G is convex. Our algorithms require O(log p) and O(log^2 p) communication rounds, respectively, and linear sequential work per round on a CGM with p processors and N\/p local memory per processor, N=|G|. The algorithms assume that N\/p &gt;= p^epsilon for some fixed epsilon &gt; 0, which is true for all commercially available multiprocessors. Our results imply BSP algorithms with O(log p) and O(log^2 p) supersteps, respectively, O(g log(p) N\/p) communication time, and O(log(p) N\/p) local computation time. Our algorithm for determining whether a bipartite graph is convex includes a novel, coarse grained parallel, version of the PQ tree data structure introduced by Booth and Lueker. Hence, our algorithm also solves, with the same time complexity as indicated above, the problem of testing the consecutive-ones property for (0,1) matrices as well as the chordal graph recognition problem. These, in turn, have numerous applications in graph theory, DNA sequence assembly, database theory, and other areas.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-99-08.pdf\">TR-99-08.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-99-08 November 1999 Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs E. Caceres, A. Chan, Frank Dehne, G. Prencipe Abstract Abstract In this paper, we present parallel algorithms for the coarse grained multicomputer (CGM) and bulk synchronous parallel computer (BSP) for solving two well known graph problems: (1) determining whether [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12244,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13010","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13010","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13010"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13010\/revisions"}],"predecessor-version":[{"id":13011,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13010\/revisions\/13011"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12244"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13010"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13010"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}