11-36
A Combinatorial Approximation Algorithm for Selecting the Gate Sizes from Finite Sets in VLSI Circuits
Preprint series: 11-36, Preprints
- MSC:
- 90B50 Management decision-making, including multiple objectives, See also {90A05, 90C31, 90D35}
- 90C27 Combinatorial optimization
Abstract: In this paper, we consider a problem of VLSI design occurring in the routing phase. The problem is to determine the optimal size selection for the gates in a combinatorial circuit which uses the problem of finding a shortest path in an oriented acyclic graph for making certain updates between any two successive iterations. For this NP-hard problem, we give an approximation algorithm.
Keywords: VLSI design, combinatorial circuits, NP-hard problems, approximation algorithm, shortest paths
The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.