Loading...
Please wait, while we are loading the content...
Similar Documents
Bounds for linear VLSI-layout problems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Müller, Rudolf |
| Copyright Year | 1993 |
| Abstract | This thesis develops structural and algorithmic approaches for the computation of bounds for optimization problems that arise in the context of linear VLSI layout styles. With the help of the new notion of alternating-acyclic mixed graphs the VLSI problems are transformed into problems on graphs. We show that technological constraints on the feasibility of the VLSI solutions can to a large extend be translated into the graph theoretical models. The second chapter shows that the problems derived this way are related to various well-known problems on graphs. For one of these problems, the-node separator problem, we prove NP-completeness already when it is restricted to the class of 3-regular graphs. Furthermore, the graph theoretic part ot this thesis subsumes, and extends at some points, known results for this type of problme, which are results on cocomparabilitity invariants of partially ordered sets, results that certain graph classes are closed with respect to the minor operation, and the fact that the problems are polynomially solvable for cographs. We then give for all the combinatorial optimization problems integer linear programming models. They serve as a basis for polyhedral investigations as well as for relaxations by Lagrangian multipliers. For the polyhedral approach we introduce two new polytopes, the transitive acyclic subdigraph polytope of a digraph and the a-transitive acyclcic subdigraph polytope of a mixed graph. For both polytopes we characterize classes of faces and give polynomial algorithms that solve the separation problem for these classes. Relations to previously studied polytopes are worked out, by that illustrating further applications of our results. For the related acyclic subdigraph polytope we show that the separation problem for the class of fence inequalities is NP-complete. Finally, we investigate two Lagrangian relaxation models of one of the VLSI problems. They lead us to special cases of well-known combinatorial optimization problems, for which we give new algorithms. We present computational results obtained for a library of industrial benchmark instances, and use these results to compare the quality of the two approaches. iii meinen Eltern und Geschwistern gewidmet iv Preface This thesis provides an illustration how methods of combinatorial optimization can be used to treat a class of optimization problems arising in a practical application. Every work in this direction seems to be confronted with nding a reasonable trade-oo between staying close to the application problems with all its various constraints on one side, and bring out mathematical models that have enough … |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
