Login
- 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
Occurrences:
- mediaTUM GesamtbestandElektronische PrüfungsarbeitenSchoolTUM School of Computation, Information and Technology
- mediaTUM GesamtbestandHochschulbibliographie2022Schools und FakultätenMathematikProfessur für Angewandte und Computergestützte Topologie (Prof. Bauer)