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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Anne Schwahn
URN (permanent link):urn:nbn:de:hbz:386-kluedo-13943
Document Type:Master's Thesis
Language of publication:English
Year of Completion:2005
Year of Publication:2005
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Tag:Cut ; Graph Theory; Heuristic ; Tree
GND-Keyword:Baum <Mathematik> ; Graphentheorie; Heuristik ; Schnitt <Mathematik>
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik
MSC-Classification (mathematics):05C05 Trees

$Rev: 12793 $