|
|
Distributed computing
Šišaj, Róbert ; Dvořák, Zdeněk (advisor) ; Novotný, Miroslav (referee)
The aim of this work is creating a system for distributed computing in smaller LAN networks. The system should provide a platform for various applications, which will be able to run parallel processing of computationally expensive tasks (e.g. searching for prime numbers, rendering video sequences, editing photographs, ...). The reader will learn about distributed systems, about their advantages and disadvantages and will get knowledge of definitions and key words from this area. The work also makes a comparison of this system and a few existing systems (SETI@home, distributed.net). An analysis of weak parts of the proposed system is included in this paper and also some ideas and thoughts on some improvements of the system in the future.
|
|
| |
|
|
Functional Data Stuctures and Algorithms
Straka, Milan ; Dvořák, Zdeněk (advisor) ; Koucký, Michal (referee) ; Brodal, Gerth (referee)
Title: Functional Data Structures and Algorithms Author: Milan Straka Institute: Computer Science Institute of Charles University Supervisor of the doctoral thesis: doc. Mgr. Zdeněk Dvořák, Ph.D, Computer Science Institute of Charles University Abstract: Functional programming is a well established programming paradigm and is becoming increasingly popular, even in industrial and commercial appli- cations. Data structures used in functional languages are principally persistent, that is, they preserve previous versions of themselves when modified. The goal of this work is to broaden the theory of persistent data structures and devise efficient implementations of data structures to be used in functional languages. Arrays are without any question the most frequently used data structure. Despite being conceptually very simple, no persistent array with constant time access operation exists. We describe a simplified implementation of a fully per- sistent array with asymptotically optimal amortized complexity Θ(log log n) and especially a nearly optimal worst-case implementation. Additionally, we show how to effectively perform a garbage collection on a persistent array. The most efficient data structures are not necessarily based on asymptotically best structures. On that account, we also focus on data structure...
|
|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (advisor) ; Dvořák, Zdeněk (referee)
We study sufficient degree conditions that force a host graph to contain a given class of trees. This setting involves some well-known problems from the area of extremal graph theory. The most famous one is the Erdős-Sós conjecture that asserts that every graph with average degree greater than k − 1 contains any tree on k + 1 vertices. Our two main results are the following. We prove an approximate version of the Erdős-Sós conjecture for dense graphs and trees with sublinear max- imum degree. We also study a natural refinement of the Loebl-Komlós-Sós conjecture and prove it is approximately true for dense graphs. Both results are based on the so-called regularity method. The second mentioned result is a joint work with T. Klimošová and D. Piguet. 1
|
|
|
Nowhere-dense classes of graphs
Tůma, Vojtěch ; Dvořák, Zdeněk (advisor) ; Mareš, Martin (referee)
In this thesis we study sparse classes of graphs and their properties usable for design of algorithms and data structures. Our specific focus is on the con- cepts of bounded expansion and tree-depth, developed in recent years mainly by J. Nešetřil and P. Ossona de Mendez. We first give a brief introduction to the theory as whole and survey tools and results from related areas of parametrised complexity and algorithmic model theory. The main part of the thesis, application of the theory, presents two new dynamic data structures. The first is for keeping a tree-depth decomposition of a graph, the second counts appearances of fixed subgraphs in a given graph. The time and space complexity of operations of both structures is guaranteed to be low when used for sparse graphs. 1
|
|
|
Generating graphs
Mohelníková, Lucie ; Dvořák, Zdeněk (advisor) ; Jelínek, Vít (referee)
Title: Generating graphs Author: Lucie Mohelníková Department: Department of Applied Mathematics Supervisor: Mgr. Zdeněk Dvořák, Ph.D., Computer Science Institute of Char- les University Abstract: The main topic of this thesis are the methods used to generate graphs from prescribed classes, especially graphs embeddable in surfaces. An im- portant technique in this context is to generate the graphs by vertex decontracti- ons. The identification of initial (irreducible) graphs is crucial for this technique. We give an overview of the results regarding the irreducible triangulations and quadrangulations of various surfaces, especially the surfaces of low genus (sphere, projective plane, Klein bottle). The main result of this work is the identification 21 irreducible triangulations which proves the result of Lawrencenko without using of information technology. Keywords: irreducible, triangulations, torus
|
|
|
Immersions and edge-disjoint linkages
Klimošová, Tereza ; Dvořák, Zdeněk (advisor) ; Kráľ, Daniel (referee)
Graph immersions are a natural counterpart to the widely studied concepts of graph minors and topological graph minors, and yet their theory is much less developed. In the present work we search for sufficient conditions for the existence of the immersions and the properties of the graphs avoiding an immersion of a fixed graph. We prove that large tree-with of 4-edge-connected graph implies the existence of immersion of any 4-regular graph on small number of vertices and that large maximum degree of 3-edge-connected graph implies existence of immersion of any 3-regular graph on small number of vertices.
|
|
|
Meze pro vzdálenostně podmíněné značkování grafů
Kupec, Martin ; Fiala, Jiří (advisor) ; Dvořák, Zdeněk (referee)
We study the complexity of the λ−L(p, q)-labelling problem for fixed λ, p, and q. The task is to assign vertices of a graph labels from the set {0, . . . , λ} such that labels of adjacent vertices differ by at least p while vertices with a common neighbor have different labels. We use two different reductions, one from the NAE-3SAT and the second one from the edge precoloring extension problem. 1
|
|
|
Petersen coloring and variants
Bílková, Hana ; Šámal, Robert (advisor) ; Dvořák, Zdeněk (referee)
The Petersen coloring of 3-regular graph G is equivalent to the normal coloring by five colors. The normal coloring is a good coloring of edges such that every edge and its four neighbours have together three or five different colors. Jaeger conjectures that every bridgeless 3-regular graph has a Petersen coloring. If the conjecture were true, it would imply other interesting statements about 3-regular graphs. In this text we investigate normal coloring by more than five colors. Jaeger theorem about nowhere-zero Z2 3 -flow implies that every bridgeless graph has normal coloring by seven colors. Independently on the Jaeger theorem, we prove the existence of normal coloring by nine colors for graphs with a bridge, a cut of size two or with a triangle. The idea of our proof comes from Andersen's proof of existence of strong coloring by ten colors for 3-regular graphs. Finally, we sketch the idea of the proof for other classes of 3-regular graphs. 1
|
|
|
Algorithms based on bounded expansion - implementation and evaluation
Rapavá, Jana ; Dvořák, Zdeněk (advisor) ; Knop, Dušan (referee)
This thesis builds upon the result that a lot of graph classes - namely classes with bounded expansion - have properties which make deciding graph problems definable in first-order logic easier. One very important example of such a problem is subgraph isomorphism. The purpose of this work is to implement and test proposed algorithm for this problem (which has a linear time complexity in relation to the size of graph we are looking for the subgraph in). Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.