Problemy cięć w grafach z parametryzowanego punktu widzenia.

W pracy rozważamy następujące dwa problemy:W pierwszym problemie, mamy dany graf G=(V,E), wierzchołek s i nieujemene liczby całkowite p,q. Pytamy się czy istnieje zbiór krawędzi C będący rozmiaru co najwyżej q, taki, że spójna składowa wierzchołka s w G-C ma rozmiar co najwyżej p. Przedstawimy algorytm dla tego problemu, działający w czasie O^{}(3.87^q), poprawiając aktualne ograniczenie.W drugim problemie, mamy dany graf G=(V,E), zbiór terminali T ⊆ V i nieujemne liczby całkowite k i q. Pytamy się czy istnieje zbiór krawędzi C będący rozmiaru co najwyżej q, taki, że każda ścieżka pomiędzy dowolnymi dwoma terminalami zawiera co najmniej k krawędzi z C. Pokażemy, że ten problem jest "fixed parameter tractable" z parametrem q, dostarczając algorytm działający w czasie O^{}(4^q).

In the thesis we study the following two problems:In the former, we are given a graph G=(V,E), a vertex s and non-negative integers p,q. We ask whether there is a set of edges C of size at most q, such that the component of s in G-C has size at most p. We present a O^{}(3.87^q) algorithm for this problem, improving previous bound.In the latter, we are given a graph G = (V, E), a set of terminals T ⊆ V and non-negative integers k and q. We ask whether there is a set of edges C of size at most q, such that every path between any two terminals contains at least k edges from C. We show that this problem is fixed parameter tractable with parameter q by providing a O^{}(4^q) algorithm.