The Library
Optimal layout of edge-weighted forests
Tools
UNSPECIFIED (1999) Optimal layout of edge-weighted forests. DISCRETE APPLIED MATHEMATICS, 90 (1-3). pp. 135-159. ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The layout problem for trees with weighted edges is motivated by the design of very-large-scale integrated circuits. Some of the nodes are fixed and the object is to position the remainder so that the total weighted edge cost is minimized. The cost of each edge is the product of its weight and its length under some appropriate norm. Optimization for planar layouts is shown to be NP-hard. If crossings are permitted, then optimal layouts under the L-1 norm can be efficiently computed. Suitable algorithms and data structures are presented, and explicit exact cost functions are given for two classes of weighted complete binary trees. (C) 1999 Elsevier Science B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Journal or Publication Title: | DISCRETE APPLIED MATHEMATICS | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0166-218X | ||||
Official Date: | 15 January 1999 | ||||
Dates: |
|
||||
Volume: | 90 | ||||
Number: | 1-3 | ||||
Number of Pages: | 25 | ||||
Page Range: | pp. 135-159 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |