|
|
Structure of flow-continuous mappings in algebraic context
Hušek, Radek ; Šámal, Robert (advisor) ; Bonamy, Marthe (referee) ; Kaiser, Tomáš (referee)
We explore the structure of the cycle space of the graphs - most notably questions about nowhere-zero flows and cycle double covers. We touch several facets of this field. First we show that there are edge 2-connected graphs which distinguish Z2 2- and Z4- connectivity (group connectivity which is a strengthening of nowhere-zero flows). Then we examine a conjecture of Matt DeVos which asserts existence of group flows given existence of a graph homomorphism between suitable Cayley graphs. We introduce a strengthening of this conjecture called strong homomorphism property (SHP for short) which allows splitting vertices (and hence a reduction to cubic graphs). We conjecture that SHP holds for every graph and the smallest group in which the graph has a nowhere- zero flow and we prove that both SHP and the original conjecture imply existence of cycle double covers with few cycles. The question we discuss the most is counting objects on graphs - especially counting circuit double covers. We shows an almost exponential lower bound for graphs on surfaces with nice embeddings and we also show that this bound does not apply to Flower snarks. Then we shows quite precise bound for flower snarks and we also improve the lower bound for planar graphs to an exponential one. Along the way we build a framework for counting...
|
|
|
Properties of interval Boolean functions
Hušek, Radek ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
|
|
|
Hybrid databases
Hušek, Radek ; Mareš, Martin (advisor) ; Lokoč, Jakub (referee)
This thesis presents design and implementation of a data structure, which tries to combine advantages of both databases and regular data structures. Main advantages of databases we try to retain are data persistence through storing data on a hard disk and working with data using transactions which allows us parallel access without danger of inconsistency. From data structures we borrow the implementation as a library of functions and the aim on simplicity and storing data in memory. Our implementation is built around the concept of (software) transactional memory; all data are stored on hard drive as log of operations. 1
|
|
|
Vertex-transitive Supergraphs
Madaj, Pavel ; Tancer, Martin (advisor) ; Hušek, Radek (referee)
In this thesis we explore ways to extend graphs to supergraphs that are vertex-transitive. We introduce a template system for their construction. This system is used to provide a construction of vertex-transitive supergraphs of exponential size for general graphs and of quadratic size for bipartite graphs. For general graphs we also provide a quadratic lower bound. We also sketch an approach that could lead to bridging the time complexity gap between the graph isomorphism problem and the problem of recognizing vertex-transitive graphs. 1
|
|
|
Expander codes
Machová, Markéta ; Mareš, Martin (advisor) ; Hušek, Radek (referee)
Error-corecting codes are used during most of data transmissions these days. To save space, we would like to use codes which are able to correct enough errors without extending the message too much. The expander codes look promising - they are asymptotically optimal, however, in practice they are just too long. Better expander constructions could be achieved via randomness con- ductors. In this thesis, we explain what conductors are and which constructions are possible for them. In the end we will convert them to expanders and almost get expander codes which are short enough for practical use but nevertheless good. 1
|
|
| |
|
|
Properties of interval Boolean functions
Hušek, Radek ; Čepek, Ondřej (advisor)
Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
|
|
|
Properties of interval Boolean functions
Hušek, Radek ; Čepek, Ondřej (advisor)
Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
|
|
|
Artificial Bee Colony
Jukl, Jan ; Pangrác, Ondřej (advisor) ; Hušek, Radek (referee)
The minimum vertex cover (MVC) problem is a well-known NP-hard prob- lem. This thesis presents the Artificial Bee Colony (ABC) algorithm and two genetic algorithm approaches to solve this problem. The ABC algorithm is an optimization algorithm based on the intelligent behaviour of a honey bee swarm. It was first proposed for unconstrained optimization problems and showed that it is superior in performance on these kinds of problems. In this thesis, the ABC algorithm has been extended to solving the minimum vertex cover problem and applied to DIMACS and BHOSLIB benchmarks. The results produced by the ABC, the binary decision diagram based genetic algorithm and the MVC-aware genetic algorithm have been compared.
|
|
|
Expander codes
Calábková, Markéta ; Mareš, Martin (advisor) ; Hušek, Radek (referee)
Wherever information is transmitted we can find error-correcting codes. LDPC (low density parity check) codes are one of frequently used classes of codes and expander codes are promising members of this class. In this work, we explain what expander code are. We also show that expander codes simulta- neously have both asymptotically optimal parameters and linear-time encoding and decoding. Unfortunately, our constructions grant us codes, which are too big for regular use, for example for packet transmission. However, we believe that with better construction of expander graphs we will be able to construct short codes with significant practical applications. 1
|
guest ::
