|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (advisor) ; Manlove, David (referee) ; Fiala, Jiří (referee)
Title: Computational Complexity in Graph Theory Author: Eva Jelínková Department: Department of Applied Mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., Department of Applied Mathematics Abstract: We address problems from graph theory, especially from the computational complexity point of view. In the first part of the thesis we address the computational complexity of problems related to Seidel's switch- ing of graphs. We prove that the problem to decide if a given graph can be switched to contain at most a given number of edges is NP-complete, even for graphs with bounded density. We thus partially answer a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014]. We also describe infinitely many graphs H such that it is NP-complete to decide if a given graph is switching-equivalent to a graph that does not contain H as an induced subgraph. We thus close an open problem of Kratochvíl, Nešetřil and Zýka [Annals of Discrete Math. 51, 1992]. In the second part of the thesis we address the topic of matchings under preferences. We focus on the housing market problem, in particular, on the model with duplicate houses. We present a 2-approximation algorithm for the maximum number of satisfied agents when the preference lists of agents are trichotomic. On the other hand, we...
|
|
|
Room Arrangement Generation
Dvořák, Ondřej ; Petříčková, Zuzana (referee) ; Jelínková, Eva (advisor)
The aim of this thesis is to create a program which generates layouts of furniture in a room on the basis of specific constraints. This program is called Spaceout and it is based on genetic algorithms. The thesis also gives a basic overview of existing programs for creating projects of interiors and exteriors. The thesis contains a programmer and user documentation of Spaceout.
|
|
| |
|
|
Screenshots of Webpages
Benhák, Tomáš ; Mareš, Martin (referee) ; Jelínková, Eva (advisor)
The aim of the thesis is to create a program for Linux that generates screenhots of webpages independently on the windowing system. The GtkMozEmbed component of the Mozilla browser is used. A part of the thesis is a modification of the GTK+ library so that the graphic output is directed to a chosen file indepently of the windowing system.
|
|
|
Bombic 2
Fišer, Karel ; Jelínková, Eva (referee) ; Lidický, Bernard (advisor)
Title: Bombic 2 Author: Karel Fišer Department: Department of Applied Mathematics Supervisor: RNDr. Bernard Lidický Supervisor's E-mail address: bernard@kam.mff.cuni.cz Abstract: The aim was to analyze the shortcomings of the first version of the game Bombic and to desing game and map editor removes these deficiencies. This concept then implement and create a programming and user documentation. As a result of the work originated programming piece, which consists of two programs. In the chapters of this work I describe in details the shortcomings of the first version, design of data storage and architecture of both programs. In chapter 6. I bring the user documentation. Read here how to install the programs, how to set up and play the game. I'm describing how to work with the map editor and how to create a new map. Keywords: Bombic, side-scrolling, arcade game, deathmatch
|
|
|
Barvení grafů pomocí mravenčí kolonie
Vámošová, Mária ; Lidický, Bernard (referee) ; Jelínková, Eva (advisor)
In the present thesis we deal with the Graph Coloring Problem. We provide an overview of the existing approaches and focus on the Ant Colony Optimization heuristics. We have selected three algorithms, implemented them and performed a set of tests on several commonly used graph instances to study their advantages and drawbacks. We also compared their results to the best known at time to nd out how much they are suitable for the problem. In this thesis we also present an original algorithm.
|
|
|
Heuristiky pro problém výměny ledviny
Böhmová, Kateřina ; Mareš, Martin (referee) ; Jelínková, Eva (advisor)
In this thesis we are dealing with the Kidney exchange game, which is a combinatorial model of the problem of distribution of living donors of kidneys to patients. More specifically, having a set of incompatible recipient-donor pairs we want to create a permutation of the donors to obtain pairs compatible for a transplantation. We require that the solution is stable, which essentially means that there is not a group of pairs such that it would be better for all of them to create another permutation just among themselves. We give an overview of known methods for finding solutions (the Top Trading Cycles algorithm and heuristics) and for testing the stability of a solution. We describe previously known results concerning the hardness of the problem. We propose to seek for a good stable solution by starting with the result of the TTC algorithm and then applying heuristics repeatedly. We use several known heuristics together with two new ones. We present results of a series of tests to show the improvement achieved by the heuristics. We also present a new algorithm for testing the stability of a solution. This algorithm runs significantly faster than the previously known one.
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this thesis, we study the computational complexity the problem S(P) for a certain graph property P: given a graph G, determine if G is switching-equivalent to a graph having P. First, we give an overview of known results, including both properties P for which S(P) is polynomial, and those for which S(P) is NP-complete. Then we show the NP-completeness of the following problem for each c (0; 1): determine if a graph G can be switched to contain a clique of size at least cn, where n is the number of vertices of G. We also study the problem if, for a xed graph H, a given graph is switching-equivalent to an H-free graph. We show that for H isomorphic to a claw, the problem is polynomial. Further, we give a characterization of graphs witching-equivalent to a K1;2-free graph by ten forbidden induced subgraphs, each having ve vertices.
|
|
| |
|
|
III/4465 Horka nad Moravou, part: street Náměstí Osvobozen
Jelínková, Eva ; Skalická, Petra (referee) ; Smělý, Martin (advisor)
The subject of my bachelor thesis is adjustment of crossroad of streets Náměstí osvobození, P.Bezruče and 1.máje. The thesis contain adjustment of strengthened places and calm road III/4465 in space of street Náměstí osvobození. That should decrease speed of vehicles and increase safety of walkers. The thesis contain solving of static traffic, bus stop, adjustment and connection walker line and public lightening.
|
guest ::
RSS feed.