Login
- Original title:
- Homologous Circulations, Voronoi Cells, and Densest Subgraphs
- Translated title:
- Homologe Zirkulationen, Voronoi-Zellen und dichteste Teilgraphen
- Author:
- Seidel, Ina
- Year:
- 2023
- Document type:
- Dissertation
- Faculty/School:
- TUM School of Computation, Information and Technology
- Advisor:
- Weltge, Stefan (Prof. Dr.)
- Referee:
- Weltge, Stefan (Prof. Dr.); Walter, Matthias (Prof. Dr.)
- Language:
- en
- Subject group:
- MAT Mathematik
- Keywords:
- polyhedra, surface-embedded graphs, homology, circulations, lattices, Voronoi cells, extension complexity, densest subgraph problem
- TUM classification:
- MAT 500; MAT 910
- Abstract:
- This thesis considers three different topics in discrete optimization from a polyhedral perspective. The first chapter deals with finding a minimum-cost, non-negative, integer circulation in a surface-embedded digraph that is homologous to a given circulation. In the second chapter, we provide lower and upper bounds on the extension complexities of Voronoi cells of lattices. The third chapter is concerned with different aspects of the densest subgraph problem.
- Translated abstract:
- Diese Arbeit betrachtet drei Themen der diskreten Optimierung aus polyedrischer Sicht. Das erste Kapitel befasst sich mit der Suche nach einer minimalen, nicht-negativen, ganzzahligen Zirkulation in einem eingebetteten Digraphen, die in einer gegebenen Homologieklasse liegt. Im zweiten Kapitel geben wir untere und obere Schranken für die Größe erweiterter Formulierungen von Voronoi-Zellen von Gittern an. Das dritte Kapitel befasst sich mit verschiedenen Aspekten dichtester Teilgraphen.
- WWW:
- https://mediatum.ub.tum.de/?id=1692898
- Date of submission:
- 11.01.2023
- Oral examination:
- 20.04.2023
- File size:
- 887454 bytes
- Pages:
- 100
- Urn (citeable URL):
- https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20230420-1692898-1-2
- Last change:
- 15.05.2023
BibTeX
Occurrences:
- mediaTUM GesamtbestandElektronische PrüfungsarbeitenSchoolTUM School of Computation, Information and Technology
- mediaTUM GesamtbestandHochschulbibliographie2023Schools und FakultätenTUM School of Computation, Information and TechnologyProfessur für Diskrete Mathematik (Prof. Weltge)