Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 18 of 18 for “"graph property"”.
-
The edit distance function: Forbidding induced powers of cycles and other questions
<p>The edit distance between two graphs on the same labeled vertex set is defined to be the size of the symmetric difference of the edge sets. The edit distance between a graph, $G$, and a graph property, $\mathcal{H}$, is the minimum edit distance between $G$ and a graph in $\mathcal{H}$. The edit …
-
Graph-Theoretic Simplicial Complexes, Hajos-type Constructions, and k-Matchings
A graph property is monotone if it is closed under the removal of edges and vertices. Given a graph G and a monotone graph property P, one can associate to the pair (G,P) a simplicial complex, which serves as a way to encode graph properties within faces of a topological space. We study these …
-
EQUILIBRIA OF LARGE GAMES AND LARGE ECONOMIES
… of pure strategy Nash equilibrium and closed graph property of finite-action large games with traits. Next, we characterize equilibrium distributions of large games with traits. The Nash equilibrium action distributions of large distributional games are also characterized. In the end, we …
-
Functions with closed graphs.
… or metric space to another that have closed graphs in the product space. Their relationship to closed, locally closed, compact, continuous and subcontinuous functions is studied in order to determine the relative strength of the closed graph condition. The paper collects and in some cases …
-
Theory of Correspondences and Games
… necessary and sufficient for the determinateness property, equilibrium existence result and closed graph property in large games and economies. Secondly, we analyze Bayesian games and prove the existence of pure strategy Bayesian equilibria in context with finite/uncountable actions. Thirdly, we …
-
An introduction to the theory of random graphs
… an introduction to the fundamentals of random graph theory. The study starts introduces the two fundamental building blocks of random graph theory, namely discrete probability and graph theory. The study starts by introducing relevant concepts probability commonly used in random graph theory- …
-
ESSAYS ON GAME THEORY
… of the existence of perfect equilibria. The property of limit admissibility as well as robustness is further discussed. In Chapter 3, we study pure-strategy Bayesian Nash equilibria in games with incomplete information, interdependent payoffs and correlated types. We identify a necessary and …
-
Τυχαίες συνδυαστικές δομές
… if an instance of random intersection graph G (n,m,p) contains or not a Hamilton cycle. We assume that the parameter p of the model is such that p=p (n,m). We show that for the range of n,m,p which the model is not trivial or equivalent to other models the graph property contains a …
-
Automated Metamodel Instance Generation Satisfying Quantitative Constraints
… thesis presents a solution that combines both graph representation and Satisfiability Modulo Theories (SMT) to the problem of metamodel instance generation. The solution consists of two approaches, the first approach presents a new foundation for generating metamodel instances by translating a …
-
Turán Problems on Non-uniform Hypergraphs
A non-uniform hypergraph H = (V, E) consists of a vertex set V and an edge set E ⊆ 2 V; the edges in E are not required to all have the same cardinality. The set of all cardinalities of edges in H is denoted by R(H), the set of edge types. For a fixed hypergraph H, the Turán density π(H) is defined …
-
Mean curvature flow of graphs with free boundaries
… the chief object of study is the evolution of graphs under mean curvature flow with free boundaries. We study both the mean curvature flow of graphs with a prescribed angle condition on a fixed smooth hypersurface Σ in Euclidean space, and the same problem with a second boundary on which we …
-
Parameterized complexity in graph theory, logic and machine learning
… like treewidth are typically associated with graph algorithms, we expand their application to solve hard problems in three distinct domains: Graph Drawing, Explainable AI (XAI), and Logic. First, the thesis addresses the Two-Page Book Embedding problem within the classical domain of Graph …
-
Efficient algorithms in quantum query complexity
… multiplication, oracle identification, and graph-property recognition. For the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum …
-
Online Decision-Making in a Randomized Environment: Stochastic Matching and Adaptive Random Graph Processes
… variant of the problem, the vertices of the graph are revealed and processed by the algorithm sequentially. We introduce a new linear program to design and analyze combinatorial algorithms which work in greater generality than that of previous works, and which also yield the best-known …
-
On Two Combinatorial Optimization Problems in Graphs: Grid Domination and Robustness
… we focus on the dominating set problem in grid graphs and present a distributed algorithm for finding near optimal dominating sets on grids. The dominating set problem is a well-studied mathematical problem in which the goal is to find a minimum size subset of vertices of a graph such that all …
-
Toward foundational advancements in temporal graph learning
Temporal graphs capture the evolving interactions that define financial systems, communication platforms, and social networks. Their continuously changing structure makes them difficult to model, yet understanding their evolution is essential for applications such as fraud detection, behavioral …
-
On Token Movement Problems
… given a fixed unchanging input instance, e.g., a graph, the usual goal is to compute a fixed subset of vertices or edges that minimizes or maximizes some objective function. In addition to unchanging instances, the static model ignores the potential existence of prior (partially feasible) …
-
Uniqueness and Complexity in Generalised Colouring
The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules. In …