{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T00:02:28Z","timestamp":1723248148140},"reference-count":0,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":730,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["MIP-9207267"],"award-info":[{"award-number":["MIP-9207267"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Given a set of terminals on the plane <jats:italic>N<\/jats:italic> = {<jats:italic>s<\/jats:italic>, <jats:italic>\u03bd<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026, <jats:italic>\u03bd<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>}, with a source terminal <jats:italic>s<\/jats:italic>, <jats:italic>a<\/jats:italic>\nRectilinear Distance\u2010Preserving Tree (RDPT) <jats:italic>T<\/jats:italic>(<jats:italic>V<\/jats:italic>, <jats:italic>E<\/jats:italic>) is defined as a tree rooted at <jats:italic>s<\/jats:italic>,\nconnecting all terminals in <jats:italic>N<\/jats:italic>. An RDPT has the property that the length of every source\nto sink path is equal to the rectilinear distance between that source and sink. A Min\u2010\nCost Rectilinear Distance\u2010Preserving Tree (MRDPT) minimizes the total wire length\nwhile maintaining minimal source to sink linear delay, making it suitable for high\nperformance interconnect applications.<\/jats:p><jats:p>This paper studies problems in the construction of RDPTs, including the following\ncontributions. A new exact algorithm for a restricted version of the problem in one\nquadrant with <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) time complexity is proposed. A novel heuristic algorithm, which\nuses optimally solvable sub\u2010problems, is proposed for the problem in a single quadrant.\nThe average and worst\u2010case time complexity for the proposed heuristic algorithm are <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3\/2<\/jats:sup>) and <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>), respectively. A 2\u2010approximation of the quadrant merging problem is proposed. The proposed algorithm has time complexity <jats:italic>O<\/jats:italic>(<jats:italic>\u03b1<\/jats:italic><jats:sup>2<\/jats:sup><jats:italic>T<\/jats:italic>(<jats:italic>n<\/jats:italic>) + <jats:italic>\u03b1<\/jats:italic><jats:sup>3<\/jats:sup>) for any constant\n\u03b1 &gt; 1, where <jats:italic>T<\/jats:italic>(<jats:italic>n<\/jats:italic>) is the time complexity of the solution of the RDPT problem on one\nquadrant. This result improves over the best previous quadrant merging solution which\nhas <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup><jats:italic>T<\/jats:italic>(<jats:italic>n<\/jats:italic>) + <jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>) time complexity.<\/jats:p><jats:p>We test our algorithms on randomly uniform point sets and compare our heuristic\nRDPT construction against a Minimum Cost Rectilinear Steiner (MRST) tree\napproximation algorithm. Our results show that RDPTs are competitive with Steiner\ntrees in total wire\u2010length when the number of terminals is less than 32. This result makes\nRDPTs suitable for VLSI routing applications. We also compare our algorithm to the\nRao\u2010Shor RDPT approximation algorithm obtaining improvements of up to 10% in\ntotal wirelength. These comparisons show that the algorithms proposed herein produce\npromising results.<\/jats:p>","DOI":"10.1155\/1998\/26574","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:57:36Z","timestamp":1190120256000},"page":"15-30","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Rectilinear Distance\u2010Preserving Trees"],"prefix":"10.1155","volume":"7","author":[{"given":"Gustavo E.","family":"T\u00e9llez","sequence":"first","affiliation":[]},{"given":"Majid","family":"Sarrafzadeh","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[1998,1]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1998\/026574.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1998\/26574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T15:22:50Z","timestamp":1723216970000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1998\/26574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1155\/1998\/26574"],"URL":"https:\/\/doi.org\/10.1155\/1998\/26574","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1998,1]]},"assertion":[{"value":"1998-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}