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.
Download full text files
Additional Services
| Author: | Anne Schwahn |
|---|---|
| URN: | urn:nbn:de:hbz:386-kluedo-13943 |
| Document Type: | Diploma Thesis |
| Language of publication: | English |
| Year of Completion: | 2004 |
| Year of Publication: | 2004 |
| Publishing Institute: | Technische Universität Kaiserslautern |
| Granting Institute: | Technische Universität Kaiserslautern |
| Date of the Publication (Server): | 2005/10/26 |
| Tag: | Cut; Graph Theory; Heuristic; Tree |
| GND-Keyword: | Heuristik; Schnitt <Mathematik>; Baum <Mathematik>; Graphentheorie |
| Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
| DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
| MSC-Classification (mathematics): | 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 |
| Licence (German): |  Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |