User: Guest  Login
If you experience problems opening the document, please try this link.
Original title:
Algorithms in Discrete Morse Theory and Combinatorial Topology
Translated title:
Algorithmen in der diskreten Morsetheorie und kombinatorischen Topologie
Author:
Rathod, Abhishek
Year:
2022
Document type:
Dissertation
Faculty/School:
Fakultät für Mathematik
Advisor:
Bauer, Ulrich (Prof. Dr.)
Referee:
Bauer, Ulrich (Prof. Dr.); Burton, Benjamin (Prof.); Edelsbrunner, Herbert (Prof. Dr.)
Language:
en
Subject group:
MAT Mathematik
TUM classification:
MAT 530
Abstract:
This dissertation is a complexity theoretic study of problems in topology. In the first part, an open question concerning the approximability of Morse matching is resolved. In the second part, certain natural problems in simple homotopy theory are shown to be W[1]-hard. The third part describes fast algorithms for computing minimum homology bases. In the fourth part, the notion of cuts is generalized from graphs to complexes, and the complexity of computing these generalized cuts is studied.
Translated abstract:
Diese Dissertation ist eine komplexitätstheoretische Untersuchung von Problemen in der Topologie. Zunächst wird eine offene Frage bezüglich der Approximierbarkeit des Morse-Matchings gelöst und ein natürliches Problem der einfachen Homotopietheorie als W[1]-schwer gezeigt. Als nächstes beschreiben wir schnelle Algorithmen zur Berechnung minimaler Homologiebasen. Schließlich verallgemeinern wir den Begriff der Schnitte von Graphen auf Komplexe und untersuchen ihre Komplexität.
WWW:
https://mediatum.ub.tum.de/?id=1632507
Date of submission:
25.10.2021
Oral examination:
13.01.2022
File size:
3925066 bytes
Pages:
242
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20220131-1632507-1-1
Last change:
20.09.2022
 BibTeX