Please use this identifier to cite or link to this item: http://dx.doi.org/10.25673/1229
Full metadata record
DC FieldValueLanguage
dc.contributor.refereeMüller-Hannemann, Matthias, Prof. Dr.-
dc.contributor.refereeRautenbach, Dieter, Prof. Dr.-
dc.contributor.authorBerger, Annabell-
dc.date.accessioned2018-09-24T10:39:11Z-
dc.date.available2018-09-24T10:39:11Z-
dc.date.issued2011-
dc.identifier.urihttps://opendata.uni-halle.de//handle/1981185920/7501-
dc.identifier.urihttp://dx.doi.org/10.25673/1229-
dc.description.abstractWir 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.-
dc.description.statementofresponsibilityvon Annabell Berger-
dc.format.extentOnline-Ressource (XIV, 115 Bl. = 3,07 mb)-
dc.language.isoeng-
dc.publisherUniversitäts- und Landesbibliothek Sachsen-Anhalt-
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/-
dc.subjectGraphentheorie-
dc.subjectNetzwerkanalyse-
dc.subjectOnline-Publikation-
dc.subjectHochschulschrift-
dc.subject.ddc000-
dc.subject.ddc510-
dc.titleDirected degree sequences-
dcterms.dateAccepted2011-12-12-
dcterms.typeHochschulschrift-
dc.typePhDThesis-
dc.identifier.urnurn:nbn:de:gbv:3:4-6768-
local.publisher.universityOrInstitutionMartin-Luther-Universität Halle-Wittenberg-
local.subject.keywordsKnotengradsequenz; Dag Realisation; graphische Sequenzen; Realisationsproblem; Uniform Sampling; Zufallsspaziergang; gerichtete Gradsequenz; Ferrers Matrix; Ferrers Diagramm; Schwellwertsequenzen-
local.subject.keywordsvertex degree sequence; dag realization; graphical sequences, realization problem; uniform sampling; random walk; directed degree sequence; Ferrers matrix; Ferrers diagram; threshold sequenceseng
local.openaccesstrue-
dc.identifier.ppn682211826-
local.accessrights.dnbfree-
Appears in Collections:Informatik, Informationswissenschaft, allgemeine Werke

Files in This Item:
File Description SizeFormat 
Directed degree sequences.pdf3.14 MBAdobe PDFThumbnail
View/Open