Parameterized Approximations of Directed Steiner Networks

• Název práce v češtině: Parametrizované aproximace orientovaných Steinerových sítí
• Název v anglickém jazyce: Parameterized Approximations of Directed Steiner Networks
• Klíčová slova: parametrizované algoritmy|Steinerova síť|aproximace|Fixed-Parameter Tractable
• Klíčová slova anglicky: parameterized algorithms|Steiner network|approximation|Fixed-Parameter Tractable
• Akademický rok vypsání: 2022/2023
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. Andreas Emil Feldmann, Dr.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 01.02.2023
• Datum zadání: 01.02.2023
• Datum potvrzení stud. oddělením: 13.06.2023
• Datum a čas obhajoby: 11.09.2023 09:00
• Datum odevzdání elektronické podoby: 20.07.2023
• Datum odevzdání tištěné podoby: 24.07.2023
• Datum proběhlé obhajoby: 11.09.2023
• Oponenti: prof. Dániel Marx, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

- 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.