
Length bounded cuts in graphs
Berg, Michal ; Kolman, Petr (advisor) ; Dvořák, Pavel (referee)
In this thesis we will focus on a problem of length bounded cut, also known as Lbounded cut. We are going to show a combinatorial algorithm for finding a minimal Lbounded cut on graphs with bounded treewidth based on dynamic programming. Then we going to show that this algorithm can also be used for finding minimal Lbounded cut on plannar graphs. We are also going to look at problem of (dG(s, t) + 1)bounded cut. This problem is known to be NPhard for general graphs. But it is an open problem whether this problem is also NPhard on plannar graphs with special vertices on the outer face. We will try to outline a way, which might lead to showing that this problem is solvable in a polynomial time.


Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
Koutecký, Martin ; Kolman, Petr (advisor) ; Fellows, Michael R. (referee) ; Tantau, Till (referee)
In the present thesis we provide compact extended formulations for a wide range of polytopes associated with the constraint satisfaction problem (CSP), monadic second order logic (MSO) on graphs, and extensions of MSO, when the given instances have bounded treewidth. We show that our extended formulations have additional useful properties, and we uncover connections between MSO and CSP. We conclude that a combination of the MSO logic, CSP and geometry provides an extensible framework for the design of compact extended formulations and parameterized algorithms for graphs of bounded treewidth. Putting our framework to use, we settle the parameterized complexity landscape for various extensions of MSO when parameterized by two important graph width parameters, namely treewidth and neighborhood diversity. We discover that the (non)linearity of the MSO extension determines the difference between fixedparameter tractability and intractability when parameterized by neighborhood diversity. Finally, we study shifted combinatorial optimization, a new nonlinear optimization framework generalizing standard combinatorial optimization, and provide initial findings from the perspective of parameterized complexity


Flows Along Paths of Bounded Length
Altmanová, Kateřina ; Kolman, Petr (advisor) ; Pangrác, Ondřej (referee)
In this bachelors's thesis we study the problem of kbounded flows, i.e. flows which can be decomposed to flow paths of lenght bounded by a constant k. We review some known results in this field of study and we mention also the problem of kbounded cut, which is a subset of edges from the flow network s. t. the flow ne twork without these edges does not have any kbounded flow. The main aim of this thesis is a detailed explaration of the article The Maximum kflow in a Network written by V. Koubek a A. Říha, published as a conference paper in Mathematical Foundations of Coputer Science 1981, pages 389397, providing an explanation of compticated passages and completition of some of the main proofs which are ommited in the paper mentioned above. The aim of completing proofs is not accomplished due to finding a serious mistake in the conference paper. Instead of completing proofs we provide a description why the algorithm in the paper does not work. 1


Online scheduling of multiprocessor jobs with preemption
Šimsa, Štěpán ; Sgall, Jiří (advisor) ; Kolman, Petr (referee)
Abstract. The thesis is devoted to the problem of online preemptive scheduling of mul tiprocessor jobs. It gives a summary of previous work on this problem. For some special variants of the problem, especially if we restrict the sizes of jobs to one and two, new results are given, both in the terms of lower bounds and in the terms of competitive al gorithms. A previously published lower bound is showed to be computed incorrectly and it is replaced by a correct lower bound in this thesis. An algorithm is presented for the special case of four processors and sizes of jobs one and two that is conjectured to achieve the best possible competitive ratio.


ACTOR AS A CREATOR OF SOUND COMPONENT IN A AUTHOR`S PROJECT
Kolman, Petr ; ČTVRTNÍK, Jan (advisor) ; ŠRÁMEK, Vratislav (referee)
The bachelor thesis contains a brief insight into the theory of music and sound on
the stage. Describes differences in the use of sound between specific types of
theater. It continues with the personal reflection of the author of the work and
describes his most crucial moments during his studies, when he met with the music
as an actor on stage, how he worked and how he benefited from it.


Approximation and Online Algorithms
Tichý, Tomáš ; Sgall, Jiří (advisor) ; Kolman, Petr (referee) ; van Stee, Rob (referee)
This thesis presents results of our research in the area of optimization problems with incomplete informationour research is focused on the online scheduling problems. Our research is based on the worstcase analysis of studied problems and algorithms; thus we use methods of the competitive analysis during our research. Althrough there are many "realworld" industrial and theoretical applications of the online scheduling problems there are still so many open problems with so simple description. Therefore it is important, interesting and also challenging to study the online scheduling problems and their simplified variants as well. In this thesis we have shown the following our results of our research on the online scheduling problems: A 1.58competitive online algorithm for the problem of randomized scheduling of unit jobs on a single processor, where the jobs are arriving over time and the total weight of processed jobs ismaximized. A lower bound 1.172 on the competitive ratio for the problem of randomized scheduling of 2uniform unit jobs on a single processor, where the jobs are arriving over time andthe totalweight of processed jobs is maximized. A lower bound 1.25 on the competitive ratio for the problem of randomized scheduling of suniform unit jobs on a single processor where s is tending to...


Algoritmy pro Lomezené toky
Voborník, Jan ; Kolman, Petr (advisor) ; Kučera, Luděk (referee)
We study the problem of maximum $L$bounded flow, a flow decomposable to flow paths of length bounded by $L$. We review the basic results and related problems. Maximum $L$bounded flow can be computed in polynomial time in networks with unit edge lengths but combinatorial algorithm is not known. We study combinatorial approach to this question. In networks with general edge lengths, the problem is \cNPhard; for this problem we describe a fully polynomial approximation scheme (FPTAS) based on an algorithm for maximum multicommodity flow. This approach is practically more efficient than the previous FPTAS which was based on the ellipsoid method. Powered by TCPDF (www.tcpdf.org)


Obtížné problémy vzhledem k parametru různorodost sousedství
Koutecký, Martin ; Kolman, Petr (advisor) ; Fiala, Jiří (referee)
Parameterized complexity is a part of computer science dealing with the computational complexity of problems measured not only by the length of their input but also some parameter of the input. Nei ghborhood diversity is a recently introduced parameter describing a certain structure of a graph. is parameter is aractive for resear especially because some problems whi are hard with respect to other parameters that are incomparable with neighborhood diversity become fixedparameter tractable with respect to neighborhood diversity. In this thesis we show fixedparameter tractability for three problems that are hard with respect to treewidth. is constitutes the main part of this thesis and it is our original work. Next it contains an overview of other interesting problems and also a survey of the state of the art in the area of parameters for sparse and dense graphs. 1


Algoritmy pro řezy v grafech
Pecsők, Ján ; Kolman, Petr (advisor) ; Tiwary, Hans Raj (referee)
Graphpartitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multicommodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called CutMatching game framework. Finally we present the performance results of our implementation of the LeightonRao and the CutMatching game algorithms. Powered by TCPDF (www.tcpdf.org)


Flows and cuts with restriction
Knop, Dušan ; Kolman, Petr (advisor) ; Krčál, Marek (referee)
Title: Flows and cuts with constraints Author: Dušan Knop Department: Department of applied mathematics Supervisor: Doc. Mgr. Petr Kolman, PhD, Department of applied mathematics Abstract: In this thesis we study the problem of length bounded cuts between two vertices of a graph. In this problem the task is to find a set of edges such that after its removal the minimal distance between the two vertices is as prescribed. The work provides a basic overview of the literature on this problem and presents it in the context of other theoretical problems. It also offers some applications of length bounded cuts and flows. We describe some heuristics for data reduction. The main result of this thesis is a polynomial time algorithm in seriesparallel graphs for problem of length bounded cut, which is NPhard in general. Keywords: cuts, seriesparallel graphs, algorithm, complexity
