|
|
An Interactive DNA Computing Simulator
Kovács, Martin ; Petrlík, Jiří (referee) ; Bidlo, Michal (advisor)
The aim of this work is to summarize the basic principles of operations performed over DNA molecules and to demonstrate their usage in solving some hard mathematical problems. In particular, the Hamiltonian Path Problem -- HPP (also known as the Traveling Salesman Problem) will be considered as a case study. A fundamental approach introduced by Leonard Adleman will be desctribed to solve the HPP using the DNA operations. His work may be considered as the first experiment in the area that is currently known as DNA computing. The goal of this bachelor thesis is to implement an interactive software simulator (based on the principles and formal models of Adleman's work) for solving the HPP and to evaluate its abilities with respect to area complexity considering various instances of HPP.
|
|
|
Computational complexity in graph theory
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee)
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
|
|
|
Computational complexity in graph theory
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee)
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
|
|
|
An Interactive DNA Computing Simulator
Kovács, Martin ; Petrlík, Jiří (referee) ; Bidlo, Michal (advisor)
The aim of this work is to summarize the basic principles of operations performed over DNA molecules and to demonstrate their usage in solving some hard mathematical problems. In particular, the Hamiltonian Path Problem -- HPP (also known as the Traveling Salesman Problem) will be considered as a case study. A fundamental approach introduced by Leonard Adleman will be desctribed to solve the HPP using the DNA operations. His work may be considered as the first experiment in the area that is currently known as DNA computing. The goal of this bachelor thesis is to implement an interactive software simulator (based on the principles and formal models of Adleman's work) for solving the HPP and to evaluate its abilities with respect to area complexity considering various instances of HPP.
|
guest ::
