{"id":12733,"date":"2021-11-17T19:18:29","date_gmt":"2021-11-18T00:18:29","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12733"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-250-graph-partitioning-using-learning-automata","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/tr-250-graph-partitioning-using-learning-automata\/","title":{"rendered":"TR-250: Graph Partitioning Using Learning Automata"},"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-250: Graph Partitioning Using Learning Automata\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-1994\/\">Technical Report<\/a> <strong>TR-250<\/strong><br>\nJuly1994<\/p>\n\n\n\n<h2 id=\"graph-partitioning-using-learning-automata\" class=\"wp-block-heading tr_t1\">Graph Partitioning Using Learning Automata<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">B. John Oommen &amp; Edward V. de St. Croix<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n\n\n\n<p>Given a graph G, we intend to partition its nodes into two sets of equal size so as to minimize the sum of the cost of the edges having end-points in different sets. This problem, called the uniform Graph Partitioning Problem (GPP), is known to be NP-Complete. In this paper we propose the first reported learning-automaton based solution to the problem. We compare this new solution to various reported schemes such as the Kernighan-Lin\u2019s algorithm, and two excellent recent heuristic methods proposed by Rolland et. al. &#8212; an extended local search algorithm and a genetic algorithm. The current automaton-based algorithm outperforms all the other schemes. We believe that it is the fastest algorithm reported to date. Additionally, our solution can also be adapted for the GPP1 in which the edge costs are not constant but random variables whose distributions are unknown.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR250.pdf\">TR-250.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-250 July1994 Graph Partitioning Using Learning Automata B. John Oommen &amp; Edward V. de St. Croix Abstract Given a graph G, we intend to partition its nodes into two sets of equal size so as to minimize the sum of the cost of the edges having end-points in different sets. This [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11914,"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-12733","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12733","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=12733"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12733\/revisions"}],"predecessor-version":[{"id":12734,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12733\/revisions\/12734"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11914"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12733"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}