|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (advisor)
This thesis is concerned with computational complexity aspects of graph homomorph- isms and related concepts. We are mainly interested in various polynomial time versus NP-complete dichotomies. These results are especially popular thanks to the seminal result of Hell and Nešetřil providing the complexity dichotomy for graph homomorph- ism problems and the recent breakthrough result proving the complexity dichotomy for constraint satisfaction problems. The thesis is divided into three parts, all unified by the common goal to provide complexity classifications of various graph homomorphism problems. The first part is about list homomorphism problems for signed graphs. We study the complexity of such problems and obtain a structural description and dichotomy first for the case of targets being signed trees and then for the so-called separable graphs. The second part focuses on graph covering projections, also known as locally bijective homomorphisms. To the best of our knowledge, we are the first to initiate cataloguing the complexity of the corresponding problems for (mutli)graphs with semi-edges. We have three larger goals here. (1) Providing the complete dichotomy for one- and two- vertex target graphs. (2) Discuss and propose the right definition of graph cover in the case of disconnected targets. (3)...
|
|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (advisor) ; Golovach, Petr (referee) ; Proskurowski, Andrzej (referee)
This thesis is concerned with computational complexity aspects of graph homomorph- isms and related concepts. We are mainly interested in various polynomial time versus NP-complete dichotomies. These results are especially popular thanks to the seminal result of Hell and Nešetřil providing the complexity dichotomy for graph homomorph- ism problems and the recent breakthrough result proving the complexity dichotomy for constraint satisfaction problems. The thesis is divided into three parts, all unified by the common goal to provide complexity classifications of various graph homomorphism problems. The first part is about list homomorphism problems for signed graphs. We study the complexity of such problems and obtain a structural description and dichotomy first for the case of targets being signed trees and then for the so-called separable graphs. The second part focuses on graph covering projections, also known as locally bijective homomorphisms. To the best of our knowledge, we are the first to initiate cataloguing the complexity of the corresponding problems for (mutli)graphs with semi-edges. We have three larger goals here. (1) Providing the complete dichotomy for one- and two- vertex target graphs. (2) Discuss and propose the right definition of graph cover in the case of disconnected targets. (3)...
|
|
|
Cooperative games with partial information
Černý, Martin ; Bok, Jan (advisor)
(english) May 21, 2021 Partially defined cooperative games are a generalisation of classical coopera- tive games in which the worth of some of the coalitions is not known. Therefore, they are one of the possible approaches to uncertainty in cooperative game the- ory. The main focus of this thesis is to collect and extend the existing results in this theory. We present results on superadditivity, convexity, positivity and 1-convexity of incomplete games. For all the aforementioned properties, a de- scription of the set of all possible extensions (complete games extending the incomplete game) is studied. Different subclasses of incomplete games are con- sidered, among others incomplete games with minimal information, incomplete games with defined upper vector or symmetric incomplete games. Some of the results also apply to fully generalised games. For superadditivity and 1-convexity, solution concepts (considering only par- tial information) are introduced and studied. Especially for 1-convexity, a thor- ough investigation of the defined solution concepts consisting of different char- acterisations is provided. 1
|
|
|
Cooperative games with partial information
Černý, Martin ; Bok, Jan (advisor) ; Zimmermann, Karel (referee)
(english) May 21, 2021 Partially defined cooperative games are a generalisation of classical coopera- tive games in which the worth of some of the coalitions is not known. Therefore, they are one of the possible approaches to uncertainty in cooperative game the- ory. The main focus of this thesis is to collect and extend the existing results in this theory. We present results on superadditivity, convexity, positivity and 1-convexity of incomplete games. For all the aforementioned properties, a de- scription of the set of all possible extensions (complete games extending the incomplete game) is studied. Different subclasses of incomplete games are con- sidered, among others incomplete games with minimal information, incomplete games with defined upper vector or symmetric incomplete games. Some of the results also apply to fully generalised games. For superadditivity and 1-convexity, solution concepts (considering only par- tial information) are introduced and studied. Especially for 1-convexity, a thor- ough investigation of the defined solution concepts consisting of different char- acterisations is provided. 1
|
|
|
Stuctural Aspects of Graph Homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (advisor) ; Hubička, Jan (referee)
This thesis is about graph-indexed random walks, Lipschitz mappings and graph homo- morphisms. It discusses connections between these notions, surveys the existing results, and shows new results. Graph homomorphism is an adjacency-preserving mapping between two graphs. Our main objects of study are graph homomorphisms to an infinite path. We are interested in two parameters: maximum range and average range. The average range of a graph is the expected size of the image of a uniformly picked random homomorphism to an infinite path. We obtain formulas for several graph classes and investigate main conjectures on this parameter. For maximum range parameter we show a general formula and an algorithm to compute it for general graphs. Besides that, we study the problem of extending a prescribed partial graph homomorphism to a full graph homomorphism. We show that this problem is polynomial in some cases. 1
|
|
|
Cooperative interval games
Bok, Jan ; Hladík, Milan (advisor) ; Valla, Tomáš (referee)
In this thesis, we study cooperative interval games, a generalized model of cooperative games in which worth of every coalition corresponds with a closed interval representing all possible outcomes of their cooperation. We give a brief introduction into classical cooperative games, interval analysis and finally introduction to cooperative interval games with focus on selections, that is on all possible outcomes of interval game with no additional uncertainty. We introduce new selection-based classes of interval games and prove their characterizations and relation to existing classes. We show a new results regarding core and imputations. We introduce a definition of strong imputation and core and examine a problem of equality of two different versions of core -- the main stability solution of cooperative interval games. Finally, we make some new remarks on Shapley value of interval games.
|
|
|
Phyllotactic Model Linking Nano and Macro World
Horáček, Miroslav ; Meluzín, Petr ; Krátký, Stanislav ; Urbánek, Michal ; Bok, Jan ; Kolařík, Vladimír
Recently, the arrangement of diffraction primitives according to a phyllotactic model was presented. This arrangement was used to benchmarking purposes of the e-beam writer nano patterning. The phyllotactic arrangement has several interesting properties. One of them is related with the coherence between the nanoor microscopic domain of individual optical primitives and the properties of visually perceived images crated by these structures in the macro domain. This paper presents theoretical analysis of the phyllotactic arrangement in the referred context. Different approaches enabling the creation of diffractive optically variable images are proposed. The practical part of the presented work deals with the nano patterning of such structures using two different types of the e-beam pattern generators. One of them is a system with a variable shaped beam of electrons, while the other one is a system with a Gaussian-shaped beam. E-beam writing strategies and the use of inherent spiral patterns for exposure ordering and partitioning are also discussed.
|
|
|
Large-area gray-scale structures in e-beam writer versus area current homogeneity and deflection uniformity
Kolařík, Vladimír ; Horáček, Miroslav ; Matějka, Milan ; Krátký, Stanislav ; Bok, Jan
The high stability and good current homogeneity in the spot of the e-beam writer is crucial to the exposure quality, particularly in the case of large-area structures when gray-scale lithography is used. Even though the deflection field distortion is calibrated regularly and beam focus and beam astigmatism is dynamically corrected over the entire deflection field,\nwe can observe disturbances in the exposed relief for both nowadays types of e-beam writers, the shaped e-beam writing system and the Gaussian e-beam writing system. A stable and homogeneous angular current density distribution in the spot is important especially in the case of shaped e-beam lithography systems. A non-homogeneity of the spot over deflection field is seen alongside the field boundaries of both lithography systems.
|
|
|
Structural Color of Metallic Surfaces
Kolařík, Vladimír ; Horáček, Miroslav ; Urbánek, Michal ; Matějka, Milan ; Krátký, Stanislav ; Chlumská, Jana ; Bok, Jan
Nano structuring of metallic surfaces shows surface colors unusual for a given material. This study presents an overview of possible approaches to achieve desirable color changes. The nano structured relief structures prepared by means of electron beam lithography process are presented. Optical design and simulation of optical properties, data preparation for e-beam patterning, parameters of the writing process, and technological issues are presented in detail. Finally, real examples of structures that exhibit surface color changes are presented and discussed.
|
|
|
Some Other Gratings: Benchmarks for Large-Area E-Beam Nanopatterning
Meluzín, Petr ; Horáček, Miroslav ; Urbánek, Michal ; Bok, Jan ; Krátký, Stanislav ; Matějka, Milan ; Chlumská, Jana ; Kolařík, Vladimír
E-beam lithography is a flexible technology for diffraction gratings origination. Nevertheless, requirements of the high optical quality of large area diffractive structures imply various severe challenges to e-beam delineating processes. This paper summarizes the e-beam process parameters that influence the quality of large area grating structures. Next, we propose some new methods to prepare diffraction gratings that were found to be useful for testing and benchmarking purposes. Those methods include single line gratings, labyrinth structures, fractional structures, tiling patterns, quasi regular filling structures and forked line structures. Various samples were prepared with the standard and newly developed e-beam patterning processes using both e-beam writers available: one with the Gaussian beam at 100 keV and another one with the shaped beam at 15 keV. Some of the results are presented further in this paper, their variants and parameters are discussed as well as their usefulness as benchmarking e-beam patterns for large area optical structures, elements and devices.
|
guest ::
RSS feed.