Buch, Deutsch, 304 Seiten
Buch, Deutsch, 304 Seiten
ISBN: 978-3-86064-363-1
Verlag: Kovac
Zunächst führt Hickl in alle graphentheoretischen und geometrischen Begriffe ein, die zur Beschreibung des Ansatzes nötig sind. Sodann befaßt er sich mit Graph-Grammatiken, insbesondere mit Ableitungen in Graph-Grammatiken, der Sprache einer Graph-Grammatik und speziellen Eigenschaften von Ableitungen und Graph-Sprachen, die zur Klassifikation der nachfolgenden Layout-Probleme herangezogen werden.
Zur Betrachtung der Layout-Graph-Grammatiken werden Restriktions-Ableitungen in Layout-Graph-Grammatiken als dynamische Entscheidungsprozesse formuliert. Dies ermöglicht die Lösung der Layout-Probleme mit Hilfe dynamischer Programmierung.
Hickl charakterisiert Kostenfunktionen, für die die Top-Down-Optimierung mittels dynamischer Programmierung lösbar ist, und gibt Lösungsverfahren, zusammen mit der benötigten Zeit-Komplexität, für geeignete Kostenfunktionen an. Die Anwendbarkeit der Charakterisierung für die Kostenfunktionen Knickzahl, Fläche und Kreuzungszahl wird aufgezeigt. Es erweist sich, daß sich viele aus der Literatur bekannte Problemstellungen als Layout-Probleme in Hickls Sinne formulieren lassen.
Dies weist auf Einsatzmöglichkeiten von Layout-Graph-Grammatiken und die Allgemeinheit des Ansatzes hin. So werden alternative Möglichkeiten diskutiert, mit Hilfe einer Layout-Graph-Grammatik eine Familie von Graphen und deren Layouts zu definieren. Im Anhang finden sich sämtliche Algorithmen und Implementationsdetails, Beispiele für die einzelnen Schritte in Top-Down-Optimierungen, sowie Laufzeit-Tabellen, Literaturverzeichnis und ein Index.
