1992 | OriginalPaper | Buchkapitel
Graph Algorithms
verfasst von : Thomas Lengauer
Erschienen in: Combinatorial Algorithms for Integrated Circuit Layout
Verlag: Vieweg+Teubner Verlag
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This chapter summarizes the results from graph theory that will be used in this book. Graphs are one of the fundamental structures treated in discrete mathematics. We begin with an extensive set of classical definitions from graph theory (Section 3.1). Then we review general algorithmic techniques for exploring graphs so as to impose structures on them (Sections 3.2 to 3.7). Subsequently, we discuss important graph problems that are used in many areas of circuit layout. In Sections 3.8 to 3.10, we consider problems of finding paths and more general connection subnetworks in graphs. Such problems occur naturally in wire routing. Path problems are also the basis of many optimization procedures, such as compaction and area minimization in floorplanning. In Sections 3.11 and 3.12, we discuss network flow and matching problems that are of special importance in circuit partitioning and detailed routing, but that also find applications in other aspects of circuit layout. In Section 3.13, we include newer material on processing hierarchically defined graphs. This material gains its significance through being the formal reflection of hierarchical circuit design (see Section 1.2.2.1). Finally, we summarize results on planar graphs (Section 3.14).