Titelaufnahme

Titel
Directed degree sequences / von Annabell Berger
VerfasserBerger, Annabell
BetreuerMüller-Hannemann, Matthias Prof. Dr. ; Rautenbach, Dieter Prof. Dr.
Erschienen2011 ; Halle, Saale : Universitäts- und Landesbibliothek Sachsen-Anhalt, 2011
UmfangOnline-Ressource (XIV, 115 Bl. = 3,07 mb)
HochschulschriftHalle, Univ., Naturwissenschaftliche Fakultät III, Diss., 2011
Anmerkung
Tag der Verteidigung: 12.12.2011
Sprache der Zusammenfassung: Deutsch
SpracheEnglisch
DokumenttypE-Book
SchlagwörterGraphentheorie / Netzwerkanalyse / Halle
URNurn:nbn:de:gbv:3:4-6768 
Zugriffsbeschränkung
 Das Dokument ist frei verfügbar.
Dateien
Directed degree sequences [3.06 mb]
Links
Nachweis
Keywords
Knotengradsequenz; Dag Realisation; graphische Sequenzen; Realisationsproblem; Uniform Sampling; Zufallsspaziergang; gerichtete Gradsequenz; Ferrers Matrix; Ferrers Diagramm; Schwellwertsequenzen
Keywords (Englisch)
vertex degree sequence; dag realization; graphical sequences realization problem; uniform sampling; random walk; directed degree sequence; Ferrers matrix; Ferrers diagram; threshold sequences
Keywords
Wir betrachten zwei Probleme der algorithmischen Graphentheorie und Netzwerkanalyse. Beim "Dag Realisationsproblem" sei eine endliche Sequenz S von Paaren natürlicher Zahlen gegeben. Gibt es einen Dag (ohne parallele Kanten und Schleifen) der S als Knotengradsequenz besitzt? Wir entwickeln für dieses NP-vollständige Problem sowohl deterministische als auch randomisierte polynomielle Algorithmen die relevante Sequenzklassen beweisbar lösen und für die restlichen Sequenzen in empirischen Experimenten ausgesprochen erfolgreich funktionieren. Für eine spezielle Klasse von Sequenzen geben wir eine vollständige Charakterisierung an. Das "Uniform Realization Sampling Problem" ist die Suche nach einer gleichverteilt gewählten Digraph Realisation (Kreise sind nun erlaubt) für eine Knotengradsequenz. Wir konzentrieren uns auf den random walk-Ansatz und zeigen dass der Zustandsdigraph in eine Anzahl isomorpher und in polynomieller Zeit identifizierbarer Komponenten zerfällt wenn wie in vielen Anwendungen nur Swaps angewendet werden. Wir schlagen einen neuen "Uniform Sampling Algorithmus" vor.