122 Pages
English

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

Description

¨ ¨TECHNISCHE UNIVERSITAT MUNCHEN¨ ¨FAKULTAT FUR INFORMATIKLehrstuhl fu¨r Efﬁziente 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 Classiﬁcation 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 deﬁnition canalso be extended to undirected weighted graphs G = (V,E,w) and weighted spanningtrees.

Subjects

Informations