{"id":{"repo_id":"freiburg-diss","oai_identifier":"oai:freidok.uni-freiburg.de:783"},"canonical_url":"https://search.dev.ndltd.org/etd/freiburg-diss/oai:freidok.uni-freiburg.de:783","repository":{"repo_id":"freiburg-diss","name":"University of Freiburg","base_url":"https://freidok.uni-freiburg.de/oai/oai2.php"},"display":{"title":"Design und Analyse stochastischer Algorithmen auf kombinatorischen Strukturen","abstract":"In der vorliegenden Arbeit werden randomisierte Algorithmen, basierend auf ergodischen Markov-Ketten, konstruiert und analysiert. Die Grundräume dieser Markov-Ketten sind endliche Mengen kombinatorischer Strukturen, wie zum Beispiel die aufspannenden Bäume eines Graphen, die eulerschen Orientierungen eines Euler-Graphen oder die 3-Färbungen eines Graphen. Ein solcher Algorithmus liefert ein zufälliges Element des Grundraumes, dessen Verteilung annähernd der stationären Verteilung der Markov Kette entspricht. Dadurch kann eine Abschätzung für die Mächtigkeit des Grundraumes ermittelt werden. Besonderen Wert wird auf die Analyse der Laufzeit dieser Algorithmen gelegt, die von der Mischzeit der jeweiligen Markov Kette dominiert wird. Hierzu werden die Methode der kanonischen Pfade, Multi-Commodity Flows, Pfad-Coupling und Vergleichsmethoden eingesetzt.","abstract_html":"In der vorliegenden Arbeit werden randomisierte Algorithmen, basierend auf ergodischen Markov-Ketten, konstruiert und analysiert. Die Grundräume dieser Markov-Ketten sind endliche Mengen kombinatorischer Strukturen, wie zum Beispiel die aufspannenden Bäume eines Graphen, die eulerschen Orientierungen eines Euler-Graphen oder die 3-Färbungen eines Graphen. Ein solcher Algorithmus liefert ein zufälliges Element des Grundraumes, dessen Verteilung annähernd der stationären Verteilung der Markov Kette entspricht. Dadurch kann eine Abschätzung für die Mächtigkeit des Grundraumes ermittelt werden. Besonderen Wert wird auf die Analyse der Laufzeit dieser Algorithmen gelegt, die von der Mischzeit der jeweiligen Markov Kette dominiert wird. Hierzu werden die Methode der kanonischen Pfade, Multi-Commodity Flows, Pfad-Coupling und Vergleichsmethoden eingesetzt.","abstract_has_math":false,"creators":["Fehrenbach, Johannes"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Rüschendorf, Ludger"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T02:21:58Z","subjects":["Mischzeitabschätzung","kanonische Pfade","Pfad-Coupling","aufspannende Bäume","eulersche Orientierungen","Markov Chain","Mixing Time","sampling approximately at random","Spanning Trees","Eulerian Orientations"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://freidok.uni-freiburg.de/data/783","outbound_label":"Repository record","outbound_source":"source_url"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Rüschendorf, Ludger"]},{"key":"dc:creator","label":"Author","values":["Fehrenbach, Johannes"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:type","label":"Dc Type","values":["DoctoralThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mischzeitabschätzung","kanonische Pfade","Pfad-Coupling","aufspannende Bäume","eulersche Orientierungen","Markov Chain","Mixing Time","sampling approximately at random","Spanning Trees","Eulerian Orientations"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In der vorliegenden Arbeit werden randomisierte Algorithmen, basierend auf ergodischen Markov-Ketten, konstruiert und analysiert. Die Grundräume dieser Markov-Ketten sind endliche Mengen kombinatorischer Strukturen, wie zum Beispiel die aufspannenden Bäume eines Graphen, die eulerschen Orientierungen eines Euler-Graphen oder die 3-Färbungen eines Graphen. Ein solcher Algorithmus liefert ein zufälliges Element des Grundraumes, dessen Verteilung annähernd der stationären Verteilung der Markov Kette entspricht. Dadurch kann eine Abschätzung für die Mächtigkeit des Grundraumes ermittelt werden. Besonderen Wert wird auf die Analyse der Laufzeit dieser Algorithmen gelegt, die von der Mischzeit der jeweiligen Markov Kette dominiert wird. Hierzu werden die Methode der kanonischen Pfade, Multi-Commodity Flows, Pfad-Coupling und Vergleichsmethoden eingesetzt.","In this thesis we design and analyze randomized algorithms based on Markov chains. The state space of these Markov chains is a set of combinatorial structures, such as the spanning trees of a graph, the Eulerian orientations of an Eulerian graph or the 3-colorings of a graph. The output of these algorithms is a random state of the Markov chain, almost accordingly to the stationary distribution. This enables us to count the elements of the state space approximately. We focus on the analysis of the running time of the algorithms, which are dominated by the mixing time of the Markov chains. The methods we use are canonical paths, multi-commodity flows, path-coupling and comparison between Markov chains."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Design und Analyse stochastischer Algorithmen auf kombinatorischen Strukturen","Design and analysis of randomized algorithms on combinatorial structures"]}]}],"canonical_facts":{"dc:contributor":["Rüschendorf, Ludger"],"dc:creator":["Fehrenbach, Johannes"],"dc:description.abstract":["In der vorliegenden Arbeit werden randomisierte Algorithmen, basierend auf ergodischen Markov-Ketten, konstruiert und analysiert. Die Grundräume dieser Markov-Ketten sind endliche Mengen kombinatorischer Strukturen, wie zum Beispiel die aufspannenden Bäume eines Graphen, die eulerschen Orientierungen eines Euler-Graphen oder die 3-Färbungen eines Graphen. Ein solcher Algorithmus liefert ein zufälliges Element des Grundraumes, dessen Verteilung annähernd der stationären Verteilung der Markov Kette entspricht. Dadurch kann eine Abschätzung für die Mächtigkeit des Grundraumes ermittelt werden. Besonderen Wert wird auf die Analyse der Laufzeit dieser Algorithmen gelegt, die von der Mischzeit der jeweiligen Markov Kette dominiert wird. Hierzu werden die Methode der kanonischen Pfade, Multi-Commodity Flows, Pfad-Coupling und Vergleichsmethoden eingesetzt.","In this thesis we design and analyze randomized algorithms based on Markov chains. The state space of these Markov chains is a set of combinatorial structures, such as the spanning trees of a graph, the Eulerian orientations of an Eulerian graph or the 3-colorings of a graph. The output of these algorithms is a random state of the Markov chain, almost accordingly to the stationary distribution. This enables us to count the elements of the state space approximately. We focus on the analysis of the running time of the algorithms, which are dominated by the mixing time of the Markov chains. The methods we use are canonical paths, multi-commodity flows, path-coupling and comparison between Markov chains."],"dc:format.medium":["application/pdf"],"dc:subject":["Mischzeitabschätzung","kanonische Pfade","Pfad-Coupling","aufspannende Bäume","eulersche Orientierungen","Markov Chain","Mixing Time","sampling approximately at random","Spanning Trees","Eulerian Orientations"],"dc:title":["Design und Analyse stochastischer Algorithmen auf kombinatorischen Strukturen","Design and analysis of randomized algorithms on combinatorial structures"],"dc:type":["DoctoralThesis"]},"updated_at":"2026-07-24T02:21:58Z"}