Minimizing Channel Density with Movable Terminals

Ronald I. Greenberg; Jau-Der Shih

doi:10.1007/BF02522820

Minimizing Channel Density with Movable Terminals

Research output: Contribution to journal › Article › peer-review

Abstract

We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

Original language	American English
Journal	Computer Science: Faculty Publications and Other Works
Volume	17
Issue number	2
DOIs	https://doi.org/10.1007/BF02522820
State	Published - Feb 1 1997

Keywords

VLSI layout
channel routing

Disciplines

Computer Sciences
Theory and Algorithms
VLSI and Circuits, Embedded and Hardware Systems

Access to Document

10.1007/BF02522820License: Unspecified

Minimizing Channel Density with Movable TerminalsFinal published version, 270 KBLicense: Unspecified

Cite this

@article{a8f88ce102d94bfea0e96fe74ef41e5a,

title = "Minimizing Channel Density with Movable Terminals",

abstract = " We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.",

keywords = "VLSI layout, channel routing",

author = "Greenberg, {Ronald I.} and Jau-Der Shih",

year = "1997",

month = feb,

day = "1",

doi = "10.1007/BF02522820",

language = "American English",

volume = "17",

journal = "Computer Science: Faculty Publications and Other Works",

number = "2",

}

TY - JOUR

T1 - Minimizing Channel Density with Movable Terminals

AU - Greenberg, Ronald I.

AU - Shih, Jau-Der

PY - 1997/2/1

Y1 - 1997/2/1

N2 - We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

AB - We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

KW - VLSI layout

KW - channel routing

UR - https://ecommons.luc.edu/cs_facpubs/153

U2 - 10.1007/BF02522820

DO - 10.1007/BF02522820

M3 - Article

VL - 17

JO - Computer Science: Faculty Publications and Other Works

JF - Computer Science: Faculty Publications and Other Works

IS - 2

ER -

Minimizing Channel Density with Movable Terminals

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this