|
|
Interval Representations of Boolean Functions
Kronus, David ; Čepek, Ondřej (advisor) ; Sgall, Jiří (referee) ; Savický, Petr (referee)
This thesis is dedicated to a research concerning representations of Boolean functions. We present the concept of a representation using intervals of integers. Boolean function f is represented by set I of intervals, if it is true just on those input vectors, which correspond to integers belonging to intervals in I, where the correspondence between vectors and integers depends on the ordering of bits determining their significancies. We define the classes of k-interval functions, which can be represented by at most k intervals with respect to a suitable ordering of variables, and we provide a full description of inclusion relations among the classes of threshold, 2-monotonic and k-interval Boolean functions (for various values of k). The possibility to recognize in polynomial time, whether a given function belongs to a specified class of Boolean functions, is another fundamental and practically important property of any class of functions. Our results concerning interval functions recognition include a proof of co-NP- hardness of the general problem and polynomial-time algorithms for several restricted variants, such as recognition of 1-interval and 2-interval positive functions. We also present an algorithm recognizing general 1-interval functions provided that their DNF representation satisfies several...
|
|
| |
|
|
Algorithms for scheduling with conflicts
Zajíček, Ondřej ; Sgall, Jiří (advisor) ; Čepek, Ondřej (referee)
Scheduling with conflicts supposes graph of conflicts. Vertices of that graph represent machines and edges represent conflicts between them. Every machine can be switched on or switched off . Two conflicting machines cannot be both switched on at the same time. At certain times new tasks arrive to speci c machines and enqueue to its input buff ers. Each machine continuously processes tasks from its input bu ffer whenever it is switched on. An algorithm decides which machines should be switched on or switched o ff at any time, obeying conflict constraints. The objective is to schedule machine switching to minimize the maximum bu er size of all processors. The problem is online, so an algorithm has to make decisions about current con ffiguration without knowledge of future tasks. In this thesis I consider the algorithm based on maximization of scalar product of work vector (vector describing con guration of machines) and vector of bu ffer lengths. I prove that this algorithm is well de ffined, finite on every input and for speciffi c graph (path of length 3) it has competitive ratio of 7=3. Further I consider possibilities of implementation of that algorithm.
|
|
|
Výpočetní složitost v teorii grafů
Ondráčková, Eva ; Kratochvíl, Jan (advisor) ; Sgall, Jiří (referee)
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this thesis, we study the computational complexity the problem S(P) for a certain graph property P: given a graph G, determine if G is switching-equivalent to a graph having P. First, we give an overview of known results, including both properties P for which S(P) is polynomial, and those for which S(P) is NP-complete. Then we show the NP-completeness of the following problem for each c (0; 1): determine if a graph G can be switched to contain a clique of size at least cn, where n is the number of vertices of G. We also study the problem if, for a xed graph H, a given graph is switching-equivalent to an H-free graph. We show that for H isomorphic to a claw, the problem is polynomial. Further, we give a characterization of graphs witching-equivalent to a K1;2-free graph by ten forbidden induced subgraphs, each having ve vertices.
|
|
| |
|
|
Online competitive algorithms for maximizing weighzed throughput of unit jobs. ITI Series 2003-172
Bartal, Y. ; Chin, F. Y. L. ; Chrobak, M. ; Fung, S. P. Y. ; Jawor, W. ; Lavi, R. ; Sgall, Jiří ; Tichý, Tomáš
We study an online buffer management problem for networks supporting Quality-of-Service (QoS) applications, equivalently as an online scheduling problem forunit-length jobs, where each job is specified by its release time, deadline, and a nonnegative weight (QoS value). The goal is to maximize the emph{weighted throughput}, that is the total weight of scheduled jobs.
|
|
| |
|
| |
|
| |
|
| |
guest ::
