An assignment algorithm with applications to integrated circuit layout
type: Item
instance of: scholarly article
title: An assignment algorithm with applications to integrated circuit layout
zbMATH Open document ID: 0583.90066
DOI: 10.1016/0166-218X(86)90064-8
author: Mikhail J. Atallah
author: Susanne E. Hambrusch
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The 2-terminal one-to-any problem, which arises in the design of layout systems, is the problem of assigning each one of n terminals positioned on the upper row of a channel (called entry terminals) to one of m terminals positioned on the lower row (called exit terminals) so that the resulting channel routing problem has minimum density. An optimal solution to this problem is known [the authors, ''On terminal assignments that minimize the density'', Techn. Report, CSD-TR-468, Purdue Univ. (1984)]. In this paper we consider a natural generalization, the 2-color one-to-any problem, in which we have two types of entry terminals, red and blue ones, and exit terminals can be assigned to either type of entry terminal. Red and blue nets created by our algorithm are allowed to run on top of each other in the routing, and the density is defined as the larger of the red density and the blue density. Its minimization is an interestig combinatorial problem. We show how to compute the best achievable density in \(O(n+m)\) time, and an assignment achieving this density in \(O((n+m)\log (n+m))\) time.
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3934771
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: data structures
zbMATH Keywords: terminal assignments
zbMATH Keywords: 2- terminal one-to-any problem
zbMATH Keywords: design of layout systems
zbMATH Keywords: channel routing problem
zbMATH Keywords: minimum density
zbMATH Keywords: optimal solution
zbMATH Keywords: 2-color one-to-any problem
MaRDI profile type: MaRDI publication profile
cites work: Q4773298
cites work: Optimal Wiring of Movable Terminals
Recommended article: Q3997942
Recommended article: Algorithms for assignment problems on an array processor
Recommended article: A graph-theoretic approach to the IC layout resizing problem
Recommended article: Q3321485
Recommended article: Q3727874
Recommended article: A framework for solving VLSI graph layout problems
Recommended article: Linear placement algorithms and applications to VLSI design
Recommended article: Q5468417
Recommended article: Q3698710
Recommended article: An algorithm for the assignment problem
description: scientific article; zbMATH DE number 3934771