By Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
Dieses Buch befasst sich mit schweren Problemen auf Graphen, für die es vermutlich keine effizienten Algorithmen gibt, und stellt verschiedene Methoden vor, wie guy mit der algorithmischen Härte solcher Probleme umgehen kann. Einerseits kann guy effiziente Algorithmen entwerfen, die sich eine geeignete Baumstruktur der Graphen zunutze machen; andererseits erlauben Fest-Parameter-Algorithmen eine effiziente Lösung, wenn gewisse Graphenparameter klein sind. Auch wenn diese Methoden nicht anwendbar sind, können die vorhandenen exakten Exponentialzeit-Algorithmen für solche schweren Probleme oft verbessert werden. Durch die leicht verständliche Darstellung, viele erklärende Abbildungen, Beispiele und Übungsaufgaben sowie die durchdachte Auswahl von Resultaten und Techniken ist dieses Buch besonders intestine für den Einsatz in der Lehre geeignet, vor allem im Masterstudium Informatik und in den höheren Semestern des Bachelorstudiums Informatik. Gleichzeitig führt es den Leser unmittelbar an die Fronten der aktuellen Forschung in diesem neuen Teilgebiet der Algorithmik heran.
Read or Download Exakte Algorithmen für schwere Graphenprobleme PDF
Similar german_3 books
HDR-Fotografie. Das umfassende Handbuch
HDR-Fotografie? Inzwischen weitläufig etabliert und nicht nur neue Marketing-Idee um neue, teuere zu verkaufen, mit der guy dann neue, tolle Bilder schießen kann. In der aktuellen Auflage seines überzeugenden HDR-Fotografie. Das umfassende Handbuch zeigt Jürgen Held auf dem neusten Stand der Technik, dass jeder mit dem entsprechenden information (erhältlich in diesem Buch) und ein wenig Geduld und Motivation selbst ultrarealistische Bilder entwickeln kann.
Dirk Kaiser entwickelt eine integrierte Theorie der Finanzintermediation in anschaulicher shape. Er analysiert und beantwortet folgende Fragen: - Warum kommen Finanzierungsbeziehungen oft nicht direkt zwischen Finanziers und Finanzierten, sondern indirekt über die establishment des Finanzintermediärs zustande?
Präferenzmessung in industriellen Verhandlungen
Initial; Einleitung; Grundlagen industrieller Verhandlungen; Verhandlungspräferenzen als Gegenstand der Verhandlungsforschung; Konzeption eines Messansatzes zur examine industrieller Verhandlungspräferenzen; Empirische Untersuchung der aufgestellten Forschungsfragen im Rahmen einer Fallstudien-Simulation; Schlussbetrachtung und Ausblick auf den weiteren Forschungsbedarf; again subject
- Die 2-cm-Flugzeugabwehrkanonen 30 und 38
- Signalverarbeitung: Analoge und digitale Signale, Systeme und Filter
- Praxiswissen Controlling: Grundlagen - Werkzeuge - Anwendungen
- Das unsagbar Gute (Roman)
- Kaffee to go - auch zum Mitnehmen!
Extra resources for Exakte Algorithmen für schwere Graphenprobleme
Sample text
2 also, ob der gegebene Graph bipartit ist. 24. Zeigen Sie, dass ein ungerichteter Graph genau dann bipartit ist, wenn er keinen Kreis ungerader L¨ange enth¨alt. 3 definiert. Ein Kreis der L¨ange m wird u¨ blicherweise mit Cm = ({v1 , . . , vm }, {{v1 , v2 }, {v2 , v3 }, . . , {vm−1 , vm }, {vm , v1 }}) bezeichnet. 25 (Kreis). 14 zeigt drei Kreise. Abb. 14. Die Kreise C3 , C4 und C6 Hamilton-Kreis Hamilton-Weg Man sagt, ein Graph enth¨alt einen Kreis, falls er einen Kreis Cm f¨ur ein m ≥ 3 als Teilgraphen enth¨alt.
Wir betrachten in diesem Buch ausschließlich Graphen mit endlichen Knoten- und endlichen Kantenmengen. Es gibt in der Literatur unterschiedliche Graphenmodelle, die sich haupts¨achlich in der Definition der Kantenmenge unterscheiden. Die beiden folgenden Varianten werden jedoch am h¨aufigsten f¨ur algorithmische Analysen verwendet. gerichteter Graph 1. In einem gerichteten Graphen (englisch: digraph, als Abk¨urzung von directed graph) G = (V, E) ist die Kantenmenge eine Teilmenge der Menge aller Knotenpaare: E ⊆ V ×V.
Gerichteter Graph 1. In einem gerichteten Graphen (englisch: digraph, als Abk¨urzung von directed graph) G = (V, E) ist die Kantenmenge eine Teilmenge der Menge aller Knotenpaare: E ⊆ V ×V. gerichtete Kante Startknoten Zielknoten ungerichteter Graph Jede gerichtete Kante (u, v) ist ein geordnetes Paar von Knoten, wobei u der Startknoten und v der Zielknoten der Kante (u, v) ist. 2. In einem ungerichteten Graphen G = (V, E) ist die Kantenmenge eine Teilmenge der Menge aller zwei-elementigen Knotenmengen: E ⊆ {{u, v} | u, v ∈ V, u = v}.