|
|
Wikipedia Page Classification
Suchý, Ondřej ; Otrusina, Lubomír (referee) ; Smrž, Pavel (advisor)
The goal of this paper is to design and implement a system for selection of Wikipedia articles relevant to a given topic in order to reduce the amount of memory taken by its offline version. The solution of this problem was achieved with use of methods from information retrieval and theirs implementation using Elasticsearch search engine. The system tries to determine the area of user's interest by given keywords and make a selection of articles from that area. This is achieved by measuring of similarity of articles and adding all articles from frequent categories in the selection. The sizes of the output files for queries over Simple English Wikipedia are usually below 30 MB.
|
|
|
Extrenal Access to the proAlpha System
Suchý, Ondřej ; Zachariášová, Marcela (referee) ; Krčma, Martin (advisor)
This work deals with main goals and principles of ERP systems. On the basis of the presented principles it presents the proALPHA ERP system and examines it in order to determine external access possibilities. The external access into the proALPHA system is the main goal of this work. The materials management module has been chosen as the part of the system to be accessed. The access will be realized via proALPHA INWB module based on Sonic ESB which is described as well. All set goals of this work were reached.
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (advisor) ; Telle, Jan Arne (referee) ; Obdržálek, Jan (referee)
Title: Parameterized Complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisor's e-mail address: honza@kam.mff.cuni.cz Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...
|
|
|
Paramterized complexity in graph theory
Suchý, Ondřej
Seidel's switching of a set of vertices of a graph is an operation which deletes the edges leaving this set from the graph and adds those edges between the set and the rest of graph that weren't in the original graph. Other edges remain untouched by this operation. Parameterized complexity asks if the exponential part of algorithms for hard problems can be bounded by some function only of selected parameters, which we assume small. In this thesis, we study the complexity of a question if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized point of view. First we give an overview of known results. Then we show fixed-parameter tractability of switching to a regular graph, a graph with bounded degree of vertices, bounded number of edges and a graph without a forbidden subgraph. We briefly introduce basic definitions and techniques of parameterized complexity.
|
|
|
Strongly Connected Steiner Subgraphs with small number of Steiner vertices
Kemény, Tamás Dávid ; Feldmann, Andreas Emil (advisor) ; Suchý, Ondřej (referee)
Title: Strongly Connected Steiner Subgraphs with Small Number of Steiner Vertices Author: Tamás Dávid Kemény Department: Department of Applied Mathematics Supervisor: Dr. Andreas Emil Feldmann, Department of Applied Mathematics Abstract: Two well-established methods of dealing with hard optimization problems have been to develop approximation and parameterized algorithms. Recent results have shown that for some problems, it is only by combining these two approaches, into so-called pa- rameterized approximation algorithms, that we are able to efficiently find solutions that are of reasonable quality. This is the viewpoint from which we study the problem known as the Strongly Connected Steiner Subgraph problem, where a set of terminal vertices of an edge-weighted directed graph needs to be strongly-connected in the cheapest way possible. Keywords: Strongly Connected Steiner Subgraphs, Parameterized Algorithms, Approxi- mation Algorithms, Bidirected Graphs iii
|
|
| |
|
|
Extrenal Access to the proAlpha System
Suchý, Ondřej ; Zachariášová, Marcela (referee) ; Krčma, Martin (advisor)
This work deals with main goals and principles of ERP systems. On the basis of the presented principles it presents the proALPHA ERP system and examines it in order to determine external access possibilities. The external access into the proALPHA system is the main goal of this work. The materials management module has been chosen as the part of the system to be accessed. The access will be realized via proALPHA INWB module based on Sonic ESB which is described as well. All set goals of this work were reached.
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (advisor) ; Telle, Jan Arne (referee) ; Obdržálek, Jan (referee)
Title: Parameterized Complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisor's e-mail address: honza@kam.mff.cuni.cz Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...
|
|
|
Paramterized complexity in graph theory
Suchý, Ondřej
Seidel's switching of a set of vertices of a graph is an operation which deletes the edges leaving this set from the graph and adds those edges between the set and the rest of graph that weren't in the original graph. Other edges remain untouched by this operation. Parameterized complexity asks if the exponential part of algorithms for hard problems can be bounded by some function only of selected parameters, which we assume small. In this thesis, we study the complexity of a question if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized point of view. First we give an overview of known results. Then we show fixed-parameter tractability of switching to a regular graph, a graph with bounded degree of vertices, bounded number of edges and a graph without a forbidden subgraph. We briefly introduce basic definitions and techniques of parameterized complexity.
|
|
|
Paramterized complexity in graph theory
Suchý, Ondřej ; Kráľ, Daniel (referee) ; Kratochvíl, Jan (advisor)
Seidel's switching of a set of vertices of a graph is an operation which deletes the edges leaving this set from the graph and adds those edges between the set and the rest of graph that weren't in the original graph. Other edges remain untouched by this operation. Parameterized complexity asks if the exponential part of algorithms for hard problems can be bounded by some function only of selected parameters, which we assume small. In this thesis, we study the complexity of a question if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized point of view. First we give an overview of known results. Then we show fixed-parameter tractability of switching to a regular graph, a graph with bounded degree of vertices, bounded number of edges and a graph without a forbidden subgraph. We briefly introduce basic definitions and techniques of parameterized complexity.
|
guest ::
