Algorithmische GraphentheorieTurau V
Gebundene Ausgabe
Graphen sind die in der Informatik am häufigsten verwendete Abstraktion. Jedes System, welches aus diskreten Zuständen oder Objekten und Beziehungen zwischen diesen besteht, kann als Graph modelliert werden. Viele Anwendungen erfordern effiziente Algorithmen zur Verarbeitung von Graphen. Dieses Lehrbuch ist eine Einführung in die algorithmische Graphentheorie. Die Algorithmen sind in kompakter Form in einer programmiersprachennahen Notation dargestellt. Eine Übertragung in eine konkrete Programmiersprache wie C++ oder Pascal ist ohne Probleme durchzuführen. Die meisten der behandelten Algorithmen sind in der dargestellten Form im Rahmen meiner Lehrveranstaltungen implementiert und getestet worden. Die praktische Relevanz der vorgestellten Algorithmen wird in vielen Anwendungen aus Gebieten wie Compilerbau, Betriebssysteme, künstliche Intelligenz, Computernetzwerke und Operation Research demonstriert. Dieses Buch ist an allejene gerichtet, die sich mit Problemen der algorithmischen Graphentheorie beschäftigen. Es richtet sich insbesondere an Studenten der Informatik und Mathematik im Grund- als auch im Hauptstudium. Die neun Kapitel decken die wichtigsten Teilgebiete der algorithmischen Gra, phentheorie ab, ohne einen Anspruch auf Vollständigkeit zu erheben. Die Auswahl der Algorithmen erfolgte nach den folgenden beiden Gesichtspunkten: kten: Zum einen sind nur solche Algorithmen berücksichtigt, die sich einfach und klar darstellen lassen und ohne großen Aufwand zu implementieren sind. Der zweite Aspekt betrifft die Bedeutung für die algorithmische Graphentheorie an sich. Bevorzugt wurden solche Algorithmen, welche entweder Grundlagen für viele andere Verfahren sind oder zentrale Probleme der Graphentheorie lösen. Unter den Algorithmen, welche diese Kriterien erfüllten, wurden die effizientesten, hinsichtlich Speicherplatz und Laufzeit dargestellt. Letztlich war die Auswahl natürlich oft eine persönliche Entscheidung.
|