{"id":14787,"date":"2022-05-28T20:11:44","date_gmt":"2022-05-29T00:11:44","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14787"},"modified":"2026-06-09T10:58:14","modified_gmt":"2026-06-09T14:58:14","slug":"tr-169-trade-offs-in-non-reversing-diameter","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/tr-169-trade-offs-in-non-reversing-diameter\/","title":{"rendered":"TR-169: Trade-Offs in Non-Reversing Diameter"},"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-169: Trade-Offs in Non-Reversing Diameter\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/\">Technical Report<\/a>&nbsp;<strong>TR-169<\/strong><br>January 1990<\/p>\n\n\n\n<h2 id=\"trade-offs-in-non-reversing-diameter\" class=\"wp-block-heading\">Trade-Offs in Non-Reversing Diameter<\/h2>\n\n\n\n<p>Hans L. Bodlaender, Gerard Tel, Nicola Santoro<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Consider a tree T with a number of extra edges (the bridges) added. We consider the notion of diameter, that is obtained by admitting only paths p with the property that for every bridge b in path p, no edge that is on the unique path (in T) between the endpoints of b is also in p or on the unique path between the two endpoints of any other bridge in p. (Such a path is called non-reversing.) We investigate the trade-off between the number of added bridges and the resulting diameter. Upper and lower bounds of the same order are obtained for all diameters of constant size, of size a( N) + 0 ( 1) or of size f(N) where f(N) grows faster than a(N). Some applications are given.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-169.pdf\">TR-169.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-169January 1990 Trade-Offs in Non-Reversing Diameter Hans L. Bodlaender, Gerard Tel, Nicola Santoro Abstract Consider a tree T with a number of extra edges (the bridges) added. We consider the notion of diameter, that is obtained by admitting only paths p with the property that for every bridge b in path p, no [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11906,"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-14787","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14787","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=14787"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14787\/revisions"}],"predecessor-version":[{"id":24542,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14787\/revisions\/24542"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11906"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14787"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14787"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}