National Repository of Grey Literature 24 records found  1 - 10nextend  jump to record: Search took 0.00 seconds. 
Computational and structural apects of interval graphs and their variants
Novotná, Jana ; Kratochvíl, Jan (advisor) ; Jelínek, Vít (referee)
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs-a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate advantages of such model by providing a subexponential-time algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomial-time...
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (advisor) ; Pangrác, Ondřej (referee)
This thesis is devoted to the outer and grounded string representations of graphs and their subclasses. A string representation of a graph is a set of strings (bounded continuous curves in a plane), where each string corresponds to one vertex of the graph. Two strings intersect each other if and only if the two corresponding vertices are adjacent in the original graph. An outer string graph is a graph with a string representation where strings are realized inside a disk and one endpoint of each string lies on the boundary of the disk. Similarly, in case of grounded string graphs the strings lie in a common half- plane with one endpoint of each string on the boundary of the half-plane. We give a summary of subclasses of grounded string graphs and proves several results about their mutual inclusions and separations. To prove those, we use an order-forcing lemma which can be used to force a particular order of the endpoints of the string on the boundary circle or boundary line. The second part of the thesis contains proof that recognition of outer string graphs is NP-hard. 1
The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (advisor) ; Fink, Jiří (referee)
A labeled embedding of a planar graph G is a pair (G, g) consisting of a planar drawing G of G and a function g assigning labels (colors) to the faces of G. We study the problem of Embedding Restriction Satisfiability (ERS) that investi- gates whether a given graph has a labeled embedding satisfying a provided set of conditions. ERS is a relatively new problem, so not much is known about it. Nevertheless, it has great potential. It generalizes several problems looking for a particular drawing of a planar graph, such as the problem of Partially Embedded Planarity. Therefore, ERS may become a focal point in the area of graph draw- ing. In this thesis, we examine the computational complexity of ERS. We show that ERS is NP-complete. After that, we look at the complexity of some specific classes of its instances. We try to locate the boundary between the NP-complete and the polynomial variants of the problem. 1
Enumeration of polyomino fillings
Karpilovskij, Mark ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
We prove two new results about 0-1-fillings of skew diagrams avoiding long increasing and decreasing chains. In the first half of the thesis, we show that for a large class of skew diagrams, there is a bijection between sparse fillings avoiding an increasing chain of fixed length and sparse fillings avoiding a decreas- ing chain of the same length. In the second half, we extend a known inequality between the number of sparse 0-1-fillings of skew diagrams avoiding an increasing chain of length 2 and a decreasing chain of length 2 to all 0-1-fillings. 1
Structural properties of hereditary permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Valtr, Pavel (referee)
A permutation class C is splittable if it is contained in a merge of its two proper subclasses, and it is 1-amalgamable if given two permutations σ, τ ∈ C, each with a marked element, we can find a permutation π ∈ C containing both σ and τ such that the two marked elements coincide. In this thesis, we study both 1-amalgamability and splittability of permutation classes. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that there is a permutation class that is both splittable and 1-amalgamable. Moreover, we show that there are infinitely many such classes. Our construction is based on the concept of LR-inflations or more generally on hereditary 2-colorings, which we both introduce here and which may be of independent interest. 1
An algorithm for extending partial planar drawings
Hora, Martin ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
This thesis studies the problem of partially embedded planarity. The input of the problem is a graph G and a planar drawing of a subgraph of G. The goal is to decide whether the drawing of the subgraph can be extended to a planar drawing of the entire graph G. It has already been proved that the partially embedded planarity problem can be solved in linear time. However, all known linear algorithms are relatively complicated. This is probably the reason that no implementation has yet been published. We will introduce a new, simpler linear algorithm that solves the problem and we will prove its correctness. Next, we will enclose an implementation of this algorithm in the C++ programming language. 1
Hereditary classes of binary matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
Interval minors of binary matrices were introduced by Jacob Fox in the study of Stanley-Wilf limits. We study what can be implied from their relation to the theory of pattern avoidance of submatrices, which is a very popular area of discrete mathematics. We start by characterizing matrices avoiding small interval minors. We then consider classes of matrices closed under interval minors and we find classes of matrices that cannot be described by a finite number of forbidden interval minors. We also define and study a variant of a classical extremal Tur'an- type question studied in the area of combinatorics of permutations and binary matrices and in combinatorial geometry. 1
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
We investigate intersection graphs of axis-aligned L-shapes (L-graphs) and their subclass, when all L- shapes have one of their endpoints on the same line - let us call this class outer-L-graphs. In the beginning we introduce some known facts about L-graphs. Then we show, that interval, circular and outerplanar graphs are subclasses of outer-L-graphs. We also characterise outer-L-graphs using ordering without forbidden patterns. Powered by TCPDF (
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross- platform implementation of all mentioned algorithms. Powered by TCPDF (
Structure and enumeration of permutation classes
Karpilovskij, Mark ; Jelínek, Vít (advisor) ; Balko, Martin (referee)
We define the operation of composing two hereditary classes of permutations using the standard composition of permutations as functions and we explore properties and structure of permutation classes considering this operation. We mostly concern ourselves with the problem of whether permutation classes can be composed from their proper subclasses. We provide examples of classes which can be composed from two proper subclasses, classes which can be composed from three but not from two proper subclasses and classes which cannot be composed from any finite number of proper subclasses. Powered by TCPDF (

National Repository of Grey Literature : 24 records found   1 - 10nextend  jump to record:
See also: similar author names
4 Jelínek, Vladimír
2 Jelínek, Vojtěch
6 Jelínek, Václav
Interested in being notified about new results for this query?
Subscribe to the RSS feed.