122 Pages

Ranking and ordering problems of spanning trees [Elektronische Ressource] / Matthias Baumgart

Gain access to the library to view online
Learn more


¨ ¨TECHNISCHE UNIVERSITAT MUNCHEN¨ ¨FAKULTAT FUR INFORMATIKLehrstuhl fu¨r Effiziente AlgorithmenRanking and Ordering Problems of Spanning TreesMatthias BaumgartVollsta¨ndiger Abdruck der von der Fakulta¨t fu¨r Informatik der Technischen Universita¨tMu¨nchen zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften (Dr. rer. nat.)genehmigten Dissertation.Vorsitzender: Univ.-Prof. Dr. H. SeidlPru¨fer der Dissertation:1. Univ.-Prof. Dr. E. W. Mayr2. Univ.-Prof. Dr. F. J. Esparza EstaunDie Dissertation wurde am 23.04.2009 bei der Technischen Universita¨t Mu¨ncheneingereicht und durch die Fakulta¨t fu¨r Informatik am 06.11.2009 angenommen.Document Classification according to ACM CCS (1998)Categories and subject descriptors:F.2.2 [Analysis of Algorithms and Problem Complexity]:⊲ Nonnumerical Algorithms and Problems⊲ Computations on Discrete StructuresG.2.1 [Discrete Mathematics]:⊲ Combinatorics⊲ Combinatorial Algorithms, Counting Problems,Permutations and CombinationsG.2.2 [Discrete Mathematics]:⊲ Graph Theory⊲ Graph Algorithms, Graph Labeling, TreesAbstractEach spanning tree T of an undirected graph G = (V,E) is represented by a vertex inthe tree graph ofG. Two of these ‘spanning tree’ vertices are connected by an edge if andonly if the corresponding spanning trees are related by an edge swap. This definition canalso be extended to undirected weighted graphs G = (V,E,w) and weighted spanningtrees.



Published by
Published 01 January 2009
Reads 18
Language English