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.
Verfasser*innenangaben: | Anne Schwahn |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-13943 |
Dokumentart: | Diplomarbeit |
Sprache der Veröffentlichung: | Englisch |
Jahr der Fertigstellung: | 2004 |
Jahr der Erstverö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: | Heuristik; Schnitt <Mathematik>; Baum <Mathematik>; Graphentheorie |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und 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 |