Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-068-86
Optimal Compaction of Multiple Two-Component Channels under River Routing
Authors: Heng, Fook-Luen, LaPaugh, Andrea S.
Date:December 1986
Pages:10
Download Formats:
Abstract:
We develop an O(kn3) time algorithm to establish the tradeoff graph of minimum total separation (i.e. width) versus spread (i.e. length) given k parallel river routing channels, each bounded by a single component at the top and bottom, and a total of n nets. This solves the two dimensional compaction problem for a special case of slicing structured layout: a single hierarchical level structure with single layer interconnections between adjacent components. It serves as a first cut toward solving the two dimensional layout compaction problem in a slicing structure with one layer interconnection.