User: Guest  Login
Original title:
Threshold Phenomena in Branching Trees and Sparse Random Graphs 
Translated title:
Phasenübergänge in Zufallsbäumen und Zufallsgraphen 
Year:
2002 
Document type:
Dissertation 
Institution:
Fakultät für Informatik 
Advisor:
Steger, Angelika (Prof. Dr.) 
Referee:
Steger, Angelika (Prof. Dr.); Goerdt, Andreas (Prof. Dr.) 
Format:
Text 
Language:
en 
Subject group:
MAT Mathematik 
Controlled terms:
Zufallsgraph; Baum ; Färbungsproblem 
TUM classification:
MAT 055d; MAT 602d 
Abstract:
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...    »
 
Translated abstract:
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...    »
 
Publication :
Universitätsbibliothek der TU München 
Oral examination:
04.02.2002 
File size:
1256062 bytes 
Pages:
180 
Last change:
04.07.2007