|
|
Hamiltonian cycles in cubic graphs
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
In this work we study the complextity of Thomasson's algorithm over a special class of cubic graphs. This algorithm nds another hamiltonian circuit, if it starts with a rst one. An open problem is the complexity of this algorithm, but a class of cubic graphs has been found, where for each graph in this class, there exists a hamiltonian circuit and an edge on it, for which Thomasson's algorithm needs exponential number of steps. The goal of this work was to gure out, if Thomasson's algorithm needs exponential number of steps for any hamiltonian circuit and any edge on graphs from this class. We succeeded in proving, that indeed is so.
|
|
|
Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
|
|
|
Fibonacci heaps - their variations and alternative data structures
Melka, Jakub ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.
|
|
|
Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
|
|
|
Auditory roughness perception and roughness as a component of environmental noise
Otčenášek, Jan ; Melka, Jakub (advisor) ; Jandák, Vojtěch (referee)
V práci byl proveden rozbor a stavu výzkumu problematiky hlukové zátěže leteckým hlukem i současné situace v praxi. Byly realizovány záznamy leteckého hluku proudových letadel během vzletu v ose dráhy letiště Václava Havla v Praze a následně byl proveden poslechový test s těmito zvuky. Předkládané podněty se lišily mírou nepříjemnosti. V poslechovém testu byla hodnocena míra nepříjemnosti, míra drsnosti, preference zvuků a byly získány popisné slovní popisy vjemů, které respondenti při poslechu leteckého hluku měli. Výstupem práce je slovník slovních deskriptorů popisujících vjemy. Byl nalezena úměrnost mezi pocitem nepříjemnosti a mírou drsnosti a byla nalezena souvislost drsnosti a dalšími charakteristikami popisujícími vnímané zvuky.: The thesis contains overview of the current reseach state and current practice in the area of environmental noise. Aircraft noise recordings of jet engined aircraft were recorded on site in the Vaclav Havel Prague airport runway axis, and a listening tests were performed. The judged stimuli deffered in the extent of unpleasantness. Listeners evalueted the level of unpleasantness, roughness, the extent of preference and also the descriptors of the judged noise (a dictionary of verbal descriptors is also one of the results of the thesis). The results indicate a link...
|
|
|
Fibonacci heaps - their variations and alternative data structures
Melka, Jakub ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.
|
|
|
Hamiltonian cycles in cubic graphs
Melka, Jakub ; Pergel, Martin (referee) ; Kratochvíl, Jan (advisor)
In this work we study the complextity of Thomasson's algorithm over a special class of cubic graphs. This algorithm nds another hamiltonian circuit, if it starts with a rst one. An open problem is the complexity of this algorithm, but a class of cubic graphs has been found, where for each graph in this class, there exists a hamiltonian circuit and an edge on it, for which Thomasson's algorithm needs exponential number of steps. The goal of this work was to gure out, if Thomasson's algorithm needs exponential number of steps for any hamiltonian circuit and any edge on graphs from this class. We succeeded in proving, that indeed is so.
|
guest ::
