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

Export metadata

Additional Services

Search Google Scholar
Metadaten
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 first Publication:2004
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution: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