{"id":12792,"date":"2021-11-21T16:58:00","date_gmt":"2021-11-21T21:58:00","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12792"},"modified":"2026-06-02T14:59:25","modified_gmt":"2026-06-02T18:59:25","slug":"tr-95-17-complexity-of-boolean-routing","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-17-complexity-of-boolean-routing\/","title":{"rendered":"TR-95-17: Complexity of Boolean Routing"},"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-95-17: Complexity of Boolean Routing\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-1995\/\">Technical Report<\/a> TR-95-17<br>\nJuly 1995<\/p>\n\n\n\n<h2 id=\"complexity-of-boolean-routing\" class=\"wp-block-heading tr_t1\">Complexity of Boolean Routing<\/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\">Evangelos Kranakis, Danny Krizanc, Jorge Urrutia<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n\n\n\n<p class=\"tr_abstract\">We use the technique of Kolmogorov complexity to obtain lower bounds for boolean routing. For any integers n, d, we construct networks G on n vertices and degree O(d), which require \u03a9(nd log d\/ log n) memory bits per router on n log d= logn routers and hence a total of\u03a9(n2d log2&nbsp;d\/ log2&nbsp;n)<br>\nmemory bits for any full information routing scheme on the graph. The lower bound is tight when log d \/ log n is constant.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-95-17.pdf\">TR-95-17.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-95-17 July 1995 Complexity of Boolean Routing Evangelos Kranakis, Danny Krizanc, Jorge Urrutia Abstract We use the technique of Kolmogorov complexity to obtain lower bounds for boolean routing. For any integers n, d, we construct networks G on n vertices and degree O(d), which require \u03a9(nd log d\/ log n) memory [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11736,"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-12792","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12792","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=12792"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12792\/revisions"}],"predecessor-version":[{"id":12793,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12792\/revisions\/12793"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12792"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}