User: Guest  Login
Original title:
Cuts, Paths, and Processes in Graphs
Translated title:
Partitionen, Pfade und Prozesse in Graphen
Author:
Gottschau, Marinus
Year:
2020
Document type:
Dissertation
Faculty/School:
Fakultät für Mathematik
Advisor:
Schulz, Andreas (Prof. Dr.)
Referee:
Schulz, Andreas (Prof. Dr.); Matuschke, Jannik (Prof. Dr.)
Language:
en
Subject group:
MAT Mathematik
TUM classification:
WIR 527d
Abstract:
This work studies several optimization problems that are defined in graphs. These include graph cuts with novel objectives, disjoint shortest paths, and three different processes on graphs. We give several polynomial time algorithms for restricted instances and analyze boundaries of complexity of the aforementioned problems. Additionally, we address questions related to graph processes such as long-term behavior. We also provide new bounds, e.g. for minimal percolating sets in bootstrap percolat...     »
Translated abstract:
In dieser Arbeit untersuchen wir verschiedene auf Graphen definierte Optimierungsprobleme. Dabei betrachten wir Partitionsprobleme mit neuen Zielfunktionen, disjunkte kürzeste Wege sowie drei verschiedene Prozesse auf Graphen. Wir entwickeln polynomielle Algorithmen für eingerschränkte Instanzen und analysieren jeweils die Komplexität der allgemeinen Probleme. Desweiteren beantworten wir extremale Fragen zum Prozessverhalten und beweisen außerdem neue Schranken, beispielsweise für die Größe perk...     »
WWW:
https://mediatum.ub.tum.de/?id=1548760
Date of submission:
01.07.2020
Oral examination:
22.09.2020
File size:
1286418 bytes
Pages:
137
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20200922-1548760-1-2
Last change:
28.10.2020
 BibTeX