velikost textu

Strongly Connected Steiner Subgraphs with small number of Steiner vertices

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Strongly Connected Steiner Subgraphs with small number of Steiner vertices
Název v češtině:
Silné souvislé Steinerovské podgrafy s malým počtem Steinerovských vrcholů
Typ:
Bakalářská práce
Autor:
Bc. Tamás Dávid Kemény
Vedoucí:
Andreas Emil Feldmann, Dr.
Oponent:
RNDr. Ondřej Suchý, Ph.D.
Id práce:
204764
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (B1801)
Obor studia:
Obecná informatika (IOIA)
Přidělovaný titul:
Bc.
Datum obhajoby:
13. 2. 2020
Výsledek obhajoby:
Velmi dobře
Jazyk práce:
Angličtina
Klíčová slova v angličtině:
strongly-connected Steiner subgraphs, parameterized algorithms, approximation algorithms, bidirected graphs
Abstract v angličtině:
Title: Strongly Connected Steiner Subgraphs with Small Number of Steiner Vertices Author: Tamás Dávid Kemény Department: Department of Applied Mathematics Supervisor: Dr. Andreas Emil Feldmann, Department of Applied Mathematics Abstract: Two well-established methods of dealing with hard optimization problems have been to develop approximation and parameterized algorithms. Recent results have shown that for some problems, it is only by combining these two approaches, into so-called pa- rameterized approximation algorithms, that we are able to efficiently find solutions that are of reasonable quality. This is the viewpoint from which we study the problem known as the Strongly Connected Steiner Subgraph problem, where a set of terminal vertices of an edge-weighted directed graph needs to be strongly-connected in the cheapest way possible. Keywords: Strongly Connected Steiner Subgraphs, Parameterized Algorithms, Approxi- mation Algorithms, Bidirected Graphs iii
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Tamás Dávid Kemény 742 kB
Stáhnout Abstrakt anglicky Bc. Tamás Dávid Kemény 121 kB
Stáhnout Posudek vedoucího Andreas Emil Feldmann, Dr. 78 kB
Stáhnout Posudek oponenta RNDr. Ondřej Suchý, Ph.D. 1.55 MB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. Martin Klazar, Dr. 152 kB