{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T04:10:02Z","timestamp":1723090202540},"reference-count":0,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":2191,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1994,1]]},"abstract":"<jats:p>We discuss a new <jats:italic>minimum density<\/jats:italic> objective for spanning and Steiner tree constructions. This formulation is\nmotivated by the minimum\u2010area layout objective, which is best achieved through balancing the usage of horizontal\nand vertical routing resources. We present two efficient heuristics for constructing low\u2010density spanning trees and\nprove that their outputs are on average within small constants of optimal with respect to both tree cost and\ndensity. Our proof techniques suggest a non\u2010uniform lower bound schema which can afford tighter estimates of\nsolution quality for a given problem instance. Furthermore, the minimum density objective can be transparently\ncombined with a number of previous interconnection objectives (e.g., minimizing tree radius or skew) without\naffecting solution quality with respect to these previous metrics. Extensive simulation results suggest that applications\nto VLSI global routing are promising.<\/jats:p>","DOI":"10.1155\/1994\/20983","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:56:35Z","timestamp":1190120195000},"page":"157-169","source":"Crossref","is-referenced-by-count":1,"title":["On the Minimum Density Interconnection TreeProblem"],"prefix":"10.1155","volume":"2","author":[{"given":"C. J.","family":"Alpert","sequence":"first","affiliation":[]},{"given":"J.","family":"Cong","sequence":"additional","affiliation":[]},{"given":"A. B.","family":"Kahng","sequence":"additional","affiliation":[]},{"given":"G.","family":"Robins","sequence":"additional","affiliation":[]},{"given":"M.","family":"Sarrafzadeh","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[1994,1]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1994\/020983.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/vlsi\/1994\/020983.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1994\/20983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T03:50:37Z","timestamp":1723089037000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1994\/20983"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":0,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1155\/1994\/20983"],"URL":"https:\/\/doi.org\/10.1155\/1994\/20983","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}