TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1989

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1989

Graph Problems related to Gate Matrix Layout and PLA Folding
Zitatschlüssel Report-223-1989
Autor Rolf H. Möhring
Buchtitel Computational Graph Theory, 1990
Seiten 17-52
Jahr 1989
Nummer 223
Herausgeber G. Tinhofer et al.
Verlag Springer-Verlag} # { Wien
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung This paper gives a survey on graph problems occuring in linear VLSI layout architectures such as gate matrix layout, folding 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, Lagrange relaxation and approximation algorithms based on on-line interval graph augmentation.
Typ der Publikation Preprint
Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe