|
|
Cache-oblivious Algorithms
Vaner, Michal ; Mareš, Martin (advisor) ; Falt, Zbyněk (referee)
In this work, we study the cache-oblivious computation model, which is inspired by the behaviour of the memory hierarchy of current computers. We study several graph algorithms and techniques of their design in this model. We consider graph searching, identifying connected components and computing maximal matching. We also study sorting and matrix multiplication as subproblems of many graph algorithms. In ad- dition to previously known algorithms, we present several new ones. We study their efficiency both by the means of asymptotic complexity and by benchmarking them on real hardware and we compare them with classical algorithms.
|
|
|
Desktop client for open social networks
Kasinec, Maroš ; Valla, Tomáš (advisor) ; Vaner, Michal (referee)
For the past decade social network sites emerged rapidly and effect not only online communication and social experience but also businesses, media and governments. However, their greatest deficiency, closed and centralized character, remains unnoticed among the general public. This thesis discusses and evaluates open and decentralized alternatives for them and draws attention to one particular - buddycloud. While leveraging the use of XMPP protocol, buddycloud with its Channel protocol appears to be a promising approach for opening ecosystem of social networks. It enables them to work in federated manner like e-mail network does today. As a contribution to the buddycloud project this thesis presents SocialDesktopClient, a desktop client for multiple social network services. It deals with modular client architecture and a Channel protocol implementation as the client's first social network service.
|
|
|
Cache-oblivious Algorithms
Vaner, Michal ; Mareš, Martin (advisor) ; Falt, Zbyněk (referee)
In this work, we study the cache-oblivious computation model, which is inspired by the behaviour of the memory hierarchy of current computers. We study several graph algorithms and techniques of their design in this model. We consider graph searching, identifying connected components and computing maximal matching. We also study sorting and matrix multiplication as subproblems of many graph algorithms. In ad- dition to previously known algorithms, we present several new ones. We study their efficiency both by the means of asymptotic complexity and by benchmarking them on real hardware and we compare them with classical algorithms.
|
|
|
Partial k-trees on surfaces
Vaner, Michal ; Valtr, Pavel (referee) ; Kratochvíl, Jan (advisor)
This work is solving the following problem: A graph G, a partial k-tree embeddable into some surface, is given. Is it possible to complete it to a k-tree in such a way that it is still embeddable? We show that this is always possible for small k (· 2) on any surface. On the contrary, for k ¸ 4, one can find a partial k-tree that is not possible to complete in this way, and for k large enough, there is no partial k-tree that could be completed. The case k = 3 makes the border case, because there is an infinite list of complete 3-trees embeddable into any surface, but not every 3-tree is embeddable. It is known that every partial 3-tree can be completed in the plane. To keep the thesis self-contained we present here the so far unpublished proof of prof. Kratochvíl and prof. Thomas. We extend this result to the projective plane. Other surfaces are still unexplored.
|
guest ::
