Benutzer: Gast  Login
Originaltitel:
Threshold Phenomena in Branching Trees and Sparse Random Graphs 
Übersetzter Titel:
Phasenübergänge in Zufallsbäumen und Zufallsgraphen 
Jahr:
2002 
Dokumenttyp:
Dissertation 
Institution:
Fakultät für Informatik 
Betreuer:
Steger, Angelika (Prof. Dr.) 
Gutachter:
Steger, Angelika (Prof. Dr.); Goerdt, Andreas (Prof. Dr.) 
Format:
Text 
Sprache:
en 
Fachgebiet:
MAT Mathematik 
Schlagworte (SWD):
Zufallsgraph; Baum ; Färbungsproblem 
TU-Systematik:
MAT 055d; MAT 602d 
Kurzfassung:
We consider phase transitions in random graphs with constant average degree, like the sudden appearance of the giant component or the giant k-core [2] at some critical average degree. Small neighbourhoods in such random graphs closely resemble branching trees. Frequently, the exact numerical values of the critical average degrees and the expected sizes of the aforementioned giant subgraphs can be `predicted' in a semi-heuristic manner from studying `corresponding' branching trees instead, which...    »
 
Übersetzte Kurzfassung:
Gegenstand unserer Untersuchungen sind Phasenübergänge in dünnen Zufallsgraphen mit konstantem durchschnittlichen Grad c. Man spricht von einem kombinatorischen Phasenübergang, wenn sich die Wahrscheinlichkeit einer Grapheigenschaft als Funktion von c an einem *kritischen Wert* asymptotisch unstetig verändert. So hat etwa die Eigenschaft von Graphen, dreifärbbar zu sein, einen solchen Phasenübergang. Dreifärbbarkeit zu entscheiden ist ein kanonisches NP-vollständiges Problem, und die Analyse des...    »
 
Veröffentlichung:
Universitätsbibliothek der TU München 
Mündliche Prüfung:
04.02.2002 
Dateigröße:
1256062 bytes 
Seiten:
180 
Letzte Änderung:
04.07.2007