Thesis (Selection of subject)

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Parameterized Approximations of Directed Steiner Networks

Thesis title in Czech:	Parametrizované aproximace orientovaných Steinerových sítí
Thesis title in English:	Parameterized Approximations of Directed Steiner Networks
Key words:	parametrizované algoritmy\|Steinerova síť\|aproximace\|Fixed-Parameter Tractable
English key words:	parameterized algorithms\|Steiner network\|approximation\|Fixed-Parameter Tractable
Academic year of topic announcement:	2022/2023
Thesis type:	diploma thesis
Thesis language:	angličtina
Department:	Department of Applied Mathematics (32-KAM)
Supervisor:	doc. Andreas Emil Feldmann, Dr.
Author:	hidden - assigned and confirmed by the Study Dept.
Date of registration:	01.02.2023
Date of assignment:	01.02.2023
Confirmed by Study dept. on:	13.06.2023
Date and time of defence:	11.09.2023 09:00
Date of electronic submission:	20.07.2023
Date of submission of printed version:	24.07.2023
Date of proceeded defence:	11.09.2023
Opponents:	prof. Dániel Marx, Ph.D.

Guidelines

This project is about parameterized approximation algorithms for the Directed Steiner Network (DSN) problem. The aim is to classify the patterns of the demand graphs that lead to different approximation ratios when allowing a running time parameterized by the number of terminals. Both algorithms and lower bounds can be proved for different classes of patterns.

References

- Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. Transactions on Algorithms.
- Andreas Emil Feldmann, Dániel Marx: The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. Transactions on Computation Theory.