### 2011-36

by Vakhania, N.; Werner, F..

**Series:** 2011-36, Preprints

- MSC:
- 90B50 Management decision making, including multiple objectives
- 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