doc. RNDr. Tomáš Valla, Ph.D.

doc. RNDr. Tomáš Valla, Ph.D.

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

Department of Theoretical Computer Science

RNDr. Tomáš Valla, Ph.D.

Ing. Martin Šlapák, Ph.D.

Department of Theoretical Computer Science

This thesis studies Vehicle Routing Problem (VRP) and its variants. We im- plement local search based algorithms for time windows variant of the problem (VRPTW) and we propose and implement a modification of genetic algorithm for solving local search based problems. We test our implementation on two sets of benchmarks and we compare our results to best-known solutions.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

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

Department of Theoretical Computer Science

Pattern matching with swaps problem is to find all occurrences of pattern in text while allowing pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions. We recently found a fatal flaw in the algorithm by [Ahmed et al.: The swap matching problem revisited, Theor. Comp. Sci. 2014] which we describe in detail. Moreover we show why this algorithm cannot be fixed in any simple way. Furthermore we devise a new algorithm which is based on different principles and we prove its correctness. Finally we generalize this algorithm to solve the wildcard pattern matching with swaps problem.

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. Tomáš Valla, Ph.D.

Ing. Zdeněk Konfršt, Ph.D.

Department of Theoretical Computer Science

This thesis studies Vehicle Routing Problem (VRP) and its variants. We also implement local search based algorithms for a capacitated version of the problem (CVRP). We propose and implement two algorithms, which are based on recently presented local search methods, that have not yet been applied to CVRP. On three sets of benchmark instances, we test our algorithms and compare them against best-known solutions and other solvers.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

Ing. Václav Blažej

Department of Theoretical Computer Science

This thesis provides an implementation of Brodal heap, a worst case efficient priority queue, along with a simple benchmark to assess its efficiency against another priority queue. The implementation is tested against an existing implementation of Fibonacci heap.

Thesis on DSpace

doc. RNDr. Tomáš Valla, Ph.D.

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

Department of Theoretical Computer Science

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

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. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

This thesis focuses on speedup and design of algorithms and data structures on RAM model with the limited size of integer. We use effective bitwise operations to achieve the speedup. The thesis shows the impact of such operations on the asymptotic complexity of selected algorithms and data structures. The data structures which are being speeded up focuses on segmental operations such as the number of elements on interval or biggest value on an interval. This thesis also focusing on greatest common divisor algorithm, Sparse Table and Number Theoretic Transform.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

Mgr. Jan Starý, Ph.D.

Department of Theoretical Computer Science

In this thesis we study the online Ramsey theory. The problem is defined as a game between Builder and Painter. They are given an arbitrary graph H and a playground of infinite number of independent vertices. On each round, Builder builds a new edge to the playground and Painter colors it either red or blue. The online Ramsey number of a graph H is the minimum number of rounds Builder needs to force a monochromatic H to appear as a subgraph of the playground. We compare the online Ramsey number to the size-Ramsey number, which is the minimum number of edges in a graph, that for arbitrary 2-edge-coloring contains a monochromatic copy of H. The size-Ramsey number upper bounds the online Ramsey number, however it seems to be difficult to show that there is an asymptotic gap between them. There is only one known result of this type, by Conlon [On-line Ramsey Numbers, SIAM J. Discrete Math. 2009], who showed that for an infinite number of complete graphs, the online Ramsey number is asymptotically smaller than the size-Ramsey number. In this thesis we describe an infinite family of trees for which the online Ramsey number is asymptotically smaller than size-Ramsey number. We also prove upper bounds for online Ramsey numbers of cycles and k-subdivided stars. And finally we provide an exact value of online Ramsey numbers of triangles versus stars restricted to connected graphs.

Thesis on DSpace