zbMATH — the first resource for mathematics

Graph problems related to gate matrix layout and PLA folding. (English) Zbl 0699.68072
Computational graph theory, Comput. Suppl. 7, 17-51 (1990).
Summary: [For the entire collection see Zbl 0698.00018.]
This paper gives a survey on graph problems occuring in linear VLSI layout architectures such as gate matrix layout, folding of programmable logic arrays, and Weinberger arrays. These include a variety of mostly independently investigated graph problems such as augmentation of a given graph to an interval graph with small clique size, node search of graphs, matching problems with side constraints, and other. We discuss implications of graph theoretic results for the VLSI layout problems and survey new research directions. New results presented include NP-hardness of gate matrix layout on chordal graphs, efficient algorithms for trees, cographs, and certain chordal graphs, Lagrangean relaxation and approximation algorithms based on on-line interval graph augmentation.

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science