User: Guest  Login
Original title:
Ranking and Ordering Problems of Spanning Trees 
Translated title:
Ranking- und Anordnungsprobleme von Spannbäumen 
Year:
2009 
Document type:
Dissertation 
Institution:
Fakultät für Informatik 
Advisor:
Mayr, Ernst W. (Prof. Dr.) 
Referee:
Mayr, Ernst W. (Prof. Dr.); Esparza Estaun, Francisco Javier (Prof. Dr.) 
Language:
en 
Subject group:
DAT Datenverarbeitung, Informatik 
Abstract:
In this thesis, we study bispanning graphs, i.e., graphs whose edge set consists of two disjoint spanning trees. In particular, we analyze this graph class with respect to a conjecture due to Mayr and Plaxton. In simple terms, this conjecture states that there exists a minimum number of spanning tree with distinct weights required that the weight function fulfills predefined properties. We are able to prove this claim for certain subclasses of all weighted bispanning graphs. Based on these findi...    »
 
Translated abstract:
In dieser Arbeit werden bispannende Graphen studiert, das heißt Graphen deren Kantenmenge aus zwei disjunkten Spannbäumen besteht. Insbesondere analysieren wir diese Graphklasse im Hinblick auf eine Vermutung von Mayr und Plaxton. Diese Vermutung besagt vereinfacht beschrieben, dass es, unter bestimmten Voraussetzungen an die Gewichtsfunktion, in jedem gewichteten bispannenden Graphen eine Mindestanzahl von Spannbäumen mit paarweise verschiedenem Gewicht gibt. Für bestimmte Teilmengen aller ge...    »
 
Oral examination:
26.11.2009 
Pages:
122 
Last change:
11.03.2010