Theses

doc. RNDr. Dušan Knop, Ph.D.

Department of Theoretical Computer Science

In the Roommate diversity problem, agents that belong to one of the two types have to be allocated to fixed size rooms based on their preferences, which depend solely on the fraction of agents of their own type among their potential roommates. In this work we study the stability of outcomes with respect to the room size and structured preferences. We provide a new randomized algorithm for finding core stable outcomes and show the results which we have obtained with the algorithm. We have found a small single-peaked instance with empty core and have verified, that every instance of the Roommate diversity problem with room size = 3, all preferences single peaked and number of agents <= 30, room size = 3 and number of agents <= 15, room size = 4, all preferences single peaked and number of agents = 30, admits an outcome that is core stable. We present arguments why we believe that every instance of this problem with room size = 3, room size = 4 and all preferences single peaked, admits an outcome that is core stable.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

In this thesis, we study the m-eternal domination problem. Given graph G, guards are placed on vertices of G. Then vertices are subject to sequential attacks. After each attack, a guard must move into the attacked vertex. At most one guard is allowed to occupy any vertex. We denote the minimum number of guards, that can defend G indefinitely as g[?]m(G). We consider cactus graphs G, such that every edge in G is on a cycle of size 3k + 1 for some k [?] N. We show that for every such G on n vertices, g[?]m(G) = 1 + (n [?] 1)/3. We introduce the m-eternal guard configuration problem, being the same as the m-eternal domination problem, except it allows multiple guards on single vertex. We denote the minimum number of required guards in G as G[?]m(G). We present a linear algorithm for computing G[?]m(G) in cactus graphs, where every articulation is in two blocks. Moreover, we design a linear-time algorithm for computing g[?]m in clique trees. We include a C++ implementation of these algorithms, together with an exponential algorithm for both problems in general graphs.

Thesis on DSpace

RNDr. Ondřej Suchý, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

RNDr. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

In this thesis, we examine several open problems in taking and breaking games under the impartial and partizan setting. We prove the existence of an impartial subtraction game with aperiodic nim-sequence and periodic outcome sequence. We also analyze the equivalence classes of subtraction games and provide a solution to one of these classes. We introduce a new taking and breaking game and partially solve it. Then we solve several partizan subtraction games and partizan pure breaking games and describe a general technique for testing arithmetic periodicity of these games. Moreover, we design some game solving algorithms for impartial taking and breaking games. We prove PSPACE-hardness for a generalized subtraction game under the impartial setting and EXPTIME-hardness under the partizan setting.

Thesis on DSpace

RNDr. Ondřej Suchý, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

Given a weighted graph and a subset of its vertices called terminals, the Steiner Tree problem is to find its connected subgraph of the minimum weight, that contains all of the given terminals. This problem is widely known to be NP-hard, and has a wide range of applications in integrated circuit design, networking, transportation and more. In our thesis, we analyze Dreyfus-Wagner, Erickson-Monma-Veinott, and Nederlof algorithms for this problem parameterized by the number of vertices, and the rank-based dynamic programming algorithm for the problem parameterized by treewidth. For all of these algorithms, we provide an optimized implementation, and compare it with other solutions by submitting our results to the PACE 2018 challenge.

Thesis on DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

The problem of d-Path Vertex Cover, d-PVC lies in determining a subset F of vertices of a given graph G=(V,E) such that G \ F does not contain a path on d vertices. The paths we aim to cover need not to be induced. It is known that the d-PVC problem is NP-complete for any d >= 2. 5-PVC is known to be solvable in O(5^k*n^O(1)) time when parameterized by the size of the solution k. In this thesis we present an iterative compression algorithm that solves the 5-PVC problem in O(4^k*n^O(1)) time.

Thesis on DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

This thesis describes a solution to the subgraph isomorphism problem using the color coding technique. The subgraph isomorphism problem, its variants, and its applications are shown. The problem of constructing a nice tree decomposition of optimal width for a given graph is addressed, as such structure is required for the corresponding approach. As a main part of the thesis, several modifications and optimizations of the original color coding algorithm are proposed. Practical result of this work is a module implemented in C designated to solve large instances of the subgraph isomorphism problem along with the enumeration of the results.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

Department of Theoretical Computer Science

This thesis studies so-called network motifs. Network motifs are connected subgraphs of a given network that occur in significantly higher frequencies than would be expected in random networks. Different approaches to finding network motifs are described and based on their analysis a new improved parallel algorithm for finding network motifs called Efise was introduced. Practical results show, that Efise offers significantly better performance than other tools and thanks to efficient parallelization method, it also achieves linear speedups, which makes it an order of magnitude faster than previous state-of-the-art tools for finding network motifs.

Thesis on DSpace