Název: Parameterized Algorithms for 2-Edge Connected Steiner Subgraphs
Překlad názvu: Parameterized Algorithms for 2-Edge Connected Steiner Subgraphs
Autoři: Sami, Sasha ; Feldmann, Andreas Emil (vedoucí práce) ; Chitnis, Rajesh (oponent)
Typ dokumentu: Diplomové práce
Rok: 2023
Jazyk: eng
Abstrakt: In the weighted Minimum 2-Edge Connected Steiner Subgraph (2-ECSS) problem, the input is a simple undirected edge-weighted graph. The task is to find a subgraph with the least cost (sum of weights of edges), such that for each pair of vertices u, v from a distinguished subset (called terminals), there exist at least two edge-disjoint u-v paths in the subgraph. We give a ran- domized XP algorithm, parameterized by the number of terminals, for weighted Minimum 2-ECSS in case of uniform edge weights, at the heart of which lies the randomized algorithm by Bj¨orklund, Husfeldt, and Taslaman (SODA 2012), for finding a shortest cycle through a given subset of vertices. A close variant of weighted Minimum 2-ECSS is the weighted Minimum 2-Edge Connected Steiner Multi-subgraph (2-ECSM) problem. In weighted Min- imum 2-ECSM, the solution subgraph can use multiple copies of each edge in the input graph, paying separately for each copy. We show that weighted Minimum 2-ECSM is polynomially equivalent to a problem called Bi-directed Strongly Connected Steiner Subgraph (BI-SCSS), for which an FPT algorithm is known due to Chitnis et al. (TALG 2021). We show that by combining the results of Jord'an (Discret. Appl. Math. 2001) and Feldmann et al. (SOSA 2022), one can obtain an FPT algorithm for weighted Minimum 2-ECSM...
Klíčová slova: parameterized algorithms|XP|fixed-parameter tractability|randomized algorithms|2-edge connected; parameterized algorithms|XP|fixed-parameter tractability|randomized algorithms|2-edge connected

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/179482

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-521123


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce