Algorithms And Data Structures

Download PDF by Bernhard Korte, Jens Vygen, Rabe Randow: Kombinatorische Optimierung: Theorie und Algorithmen

By Bernhard Korte, Jens Vygen, Rabe Randow

ISBN-10: 3540769188

ISBN-13: 9783540769187

Dieses umfassende Lehrbuch ?ber kombinatorische Optimierung ist die deutsche ?bersetzung der vierten, wesentlich erweiterten Auflage des Buches „Combinatorial Optimization – conception and Algorithms", dessen erste Auflage im Jahr 2000 erschienen ist. Es ist aus verschiedenen Vorlesungen ?ber kombinatorische Optimierung und Spezialvorlesungen f?r Fortgeschrittene hervorgegangen, die die Autoren an der Universit?t Bonn gehalten haben.

Das Buch enth?lt vornehmlich theoretische Resultate und detaillierte Algorithmen mit beweisbar guten Laufzeiten und Ergebnissen, aber keine Heuristiken. Es werden vollst?ndige Beweise, auch f?r viele tiefe und neue Resultate gegeben, von denen einige bisher in der Lehrbuchliteratur noch nicht erschienen sind. Ferner enth?lt das Buch viele ?bungsaufgaben und ein umfassendes Literaturverzeichnis. Es gibt den neuesten Stand der kombinatorischen Optimierung wieder.

Aus den Besprechungen der englischen Auflagen:

"This booklet on combinatorial optimization is a gorgeous instance of the correct textbook."

Operations examine Letters 33 (2005), p.216-217

Show description

Read or Download Kombinatorische Optimierung: Theorie und Algorithmen PDF

Best algorithms and data structures books

Quentin F. Miller Russ;Stout's Parallel algorithms for regular architectures: meshes and PDF

Parallel-Algorithms for normal Architectures is the 1st booklet to pay attention completely on algorithms and paradigms for programming parallel desktops corresponding to the hypercube, mesh, pyramid, and mesh-of-trees. Algorithms are given to resolve basic initiatives equivalent to sorting and matrix operations, in addition to difficulties within the box of picture processing, graph idea, and computational geometry.

Read e-book online Reporting District-Level NAEP Data PDF

The nationwide overview of schooling development (NAEP) has earned a name as one of many nation's most sensible measures of scholar success in key topic components. when you consider that its inception in 1969, NAEP has summarized educational functionality for the state as an entire and, starting in 1990, for the person states.

Extra resources for Kombinatorische Optimierung: Theorie und Algorithmen

Sample text

2. 13. Sei T ein Digraph, dessen zugrunde liegender ungerichteter Graph ein Baum ist. Sei ferner U eine endliche Menge und ϕ : U → V (T ). Wir setzen F := {Se : e ∈ E(T )}, wobei wir f¨ur jedes e = (x, y) Se := {s ∈U : ϕ(s) ist in derselben Zusammenhangskomponente von T−e wie y} definieren. Dann nennt man (T, ϕ) eine Baumdarstellung von (U, F ). Siehe Beispiele in Abb. 2(b). 14. Sei (U, F ) ein Mengensystem mit einer Baumdarstellung (T, ϕ). Dann ist (U, F ) kreuzungsfrei. Ist T eine Arboreszenz, so ist (U, F ) laminar.

Vk , ek , v1 ein (geschlossener) Spaziergang mit vi = v j f¨ur 1 ≤ i < j ≤ k ist. Ein einfacher Induktionsbeweis zeigt, dass die Kantenmenge eines geschlossenen Spaziergangs in eine Familie von Kreis-Kantenmengen zerlegt werden kann. Die L¨ange eines Weges oder Kreises ist die Anzahl seiner Kanten. Ist ein Weg oder Kreis ein Teilgraph von G, so spricht man von einem Weg oder Kreis in G. Ein aufspannender Weg in G heißt hamiltonscher Weg und ein aufspannender Kreis in G heißt Hamilton-Kreis. Enth¨alt ein Graph einen Hamilton-Kreis, so heißt er hamiltonscher Graph.

Sei e die letzte nicht auch zu Q geh¨orende Kante von P. Dann ist nach dem Entfernen von e jeder Knoten weiterhin von r aus erreichbar. 3(b) ist dies ein Widerspruch zur Minimalit¨at in (e). (f)⇒(g)⇒(a): Diese Implikationen sind trivial. Ein Schnitt in einem ungerichteten Graphen G ist eine Kantenmenge vom Typ δ(X) f¨ur ∅ = X ⊂ V (G). In einem Digraphen G ist δ + (X) ein gerichteter Schnitt, falls ∅ = X ⊂ V (G) und δ − (X) = ∅, d. h. keine Kante endet in X. Wir sagen, dass eine Kantenmenge F ⊆ E(G) zwei Knoten s und t trennt, falls t von s aus in G, aber nicht in (V (G), E(G)\ F) erreichbar ist.

Download PDF sample

Kombinatorische Optimierung: Theorie und Algorithmen by Bernhard Korte, Jens Vygen, Rabe Randow


by Brian
4.3

Rated 4.00 of 5 – based on 47 votes