Minimum Fundamental Cut Basis Problem

  • Any tree in an undirected graph defines a fundamental cut basis. The minimum fundamental cut basis problem is to find a tree minimizing the weight of the corresponding basis. This problem is NP, in the thesis heuristics, relaxations, and numerical results are presented.
  • In einem ungerichteten Graphen erzeugt jeder Baum eine fundamentale Schnittbasis. Das Fundamentalschnittproblem besteht darin, einen Baum zu finden, der das Gewicht der entsprechenden Basis minimiert. Dieses Problem ist NP, in der Arbeit werden Heuristiken und Relaxierungen sowie numerische Ergebnisse vorgestellt.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Anne Schwahn
URN (Permalink):urn:nbn:de:hbz:386-kluedo-13943
Dokumentart:Diplomarbeit
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2004
Jahr der Veröffentlichung:2004
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):26.10.2005
Freies Schlagwort / Tag:Cut ; Graph Theory; Heuristic ; Tree
GND-Schlagwort:Baum <Mathematik> ; Graphentheorie; Heuristik ; Schnitt <Mathematik>
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Klassifikation (Mathematik):05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C05 Trees
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $