1. osnaDocs
  2. Fachbereich 06 - Mathematik / Informatik / Physik
  3. FB06 - E-Dissertationen

Approximation Algorithms for Multistage Subgraph Problems

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.48693/450
Open Access logo originally created by the Public Library of Science (PLoS)
Langanzeige der Metadaten
DC ElementWertSprache
dc.contributor.advisorProf. Dr. Markus Chimaniger
dc.creatorTroost, Niklas Johannes-
dc.date.accessioned2024-01-17T10:38:10Z-
dc.date.available2024-01-17T10:38:10Z-
dc.date.issued2024-01-17T10:38:10Z-
dc.identifier.urihttps://doi.org/10.48693/450-
dc.identifier.urihttps://osnadocs.ub.uni-osnabrueck.de/handle/ds-2024011710256-
dc.description.abstractThe concepts of classical graph theory offer a framework for modeling problems from almost all areas of life. Temporal graphs in particular provide a way to represent and analyze dynamic data, enabling algorithmic solutions to problems dealing with structures that change over time. For the extension to time-related data, different modifications of the graph concept can be useful, depending on the optimization goal. In this work, the focus is on the analysis of problems on finite sequences of graphs whose sequence members are to be read as snapshots of the same graph at different points in time. The key topic is to solve a given combinatorial optimization problem on a sequence of graphs such that the resulting solution sequence satisfies two conditions: (i) each solution is optimal for its respective graph and (ii) solutions of successive graphs are as similar as possible. Problems of this abstract form are called multistage problems, since their instances consist of multiple stages. First, the classical assignment problem Maximum Matching is exemplarily transferred into such a multistage setting. For the two resulting problems MIM and MUM, various approximation algorithms and reductions are developed. The algorithmic approaches for MIM can be generalized to apply to a broad class of multistage formulations of classical problems in graph theory. This general class of problems on multistage graphs, the so-called Multistage Subgraph Problems, is the focus of the second part of this thesis. After discussing the corresponding definitions and adapted algorithms, we present numerous examples of MSPs, where these adapted algorithms can be applied. As we also study the complexity of each example, this provides an overview of the similarities and differences of such multistage problems. In a third part, the performance of the approximation algorithms in practice is investigated by applying them to example instances for the Multistage Shortest Path problem. A comparison is made with derived heuristics and an exact (but slow) algorithm, investigating their respective solution quality and running time. Additional problem-specific results on Multistage Shortest Path and Multistage Minimum Weight Spanning Tree complete the thesis.eng
dc.rightsAttribution 3.0 Germany*
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/de/*
dc.subjectMultistage Graphseng
dc.subjectComplexity Theoryeng
dc.subjectApproximation Algorithmseng
dc.subject.ddc004 - Informatikger
dc.titleApproximation Algorithms for Multistage Subgraph Problemseng
dc.typeDissertation oder Habilitation [doctoralThesis]-
thesis.locationOsnabrück-
thesis.institutionUniversität-
thesis.typeDissertation [thesis.doctoral]-
thesis.date2023-11-21-
orcid.creatorhttps://orcid.org/0000-0001-7412-2770-
dc.contributor.refereeProf. Dr. Christian Komusiewiczger
dc.subject.bk54.10 - Theoretische Informatikger
dc.subject.ccsF.2.0 - Generalger
Enthalten in den Sammlungen:FB06 - E-Dissertationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis_troost.pdfPräsentationsformat1,57 MBAdobe PDF
thesis_troost.pdf
Miniaturbild
Öffnen/Anzeigen
Zur Kurzanzeige


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons