Directed degree sequences

Abstract

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.