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 15 of 15 for “"games on graphs"”.
-
Combinatorial Games on Graphs
Combinatorial Games are intriguing and have a tendency to engross students and lead them into a serious study of mathematics. The engaging nature of games is the basis for this thesis. Two combinatorial games and some educational tools are presented which were developed by the author in the pursuit …
-
Two-player games on graphs
… thesis we study different kinds of combinatorial games between two players, which are played on a board that consists of the edges of some given graph G. We distinguish unbiased games, in which both players claim/orient one edge in each round, and b-biased games in which the second player …
-
Robbing, surfing and rioting games on graphs
… μελετάται η Αιώνια Κυριαρχία (Eternal Domination). Μια ομάδα φρουρών πρέπει να κυριαρχεί αιώνια πάνω σε ένα γράφημα και έτσι να προστατεύει ενάντια επιθέσεων σε οποιονδήποτε κόμβο. Λαμβάνονται υπόψη θέματα συνδυαστικής και πολυπλοκότητας.
-
Deep Reinforcement Learning for Adversarial Games on Graphs
… robbers is a multi-agent adversarial game played on graphs. Previous research on agent strategies for this game has focused on designing heuristics for minimax strategies and often imposes strict restrictions on the graph structure. This thesis develops a methodology that instead uses Deep …
-
Games on graphs, visibility representations, and graph colorings
"In this thesis we study combinatorial games on graphs and some graph parameters whose consideration was inspired by an interest in the symmetry of hypercubes. A capacity function f on a graph G assigns a nonnegative integer to each vertex of V(G). An f-matching in G is a set M ⊆ E(G) such that the …
-
Complexity in Infinite Games on Graphs and Temporal Constraint Networks
This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. Particularly, we shall focus on game theoretical methods in order to obtain improved complexity bounds and faster algorithms for the …
-
On Euler Tours in Streaming Models and some Games on Graphs
… an Euler tour in a graph, prove a tight bound on the capture time in the Bridge-Burning Cops and Robbers Game and solve an open problem for the Extreme Vertex Destruction Model. In Chapter 2, we consider the classical Euler tour problem and take a modern look at this problem in the context of …
-
Divisors on graphs, binomial and monomial ideals, and cellular resolutions
We study various binomial and monomial ideals arising in the theory of divisors, orientations, and matroids on graphs. We use ideas from potential theory on graphs and from the theory of Delaunay decompositions for lattices to describe their minimal polyhedral cellular free resolutions. We show …
-
Positional and Detection Games
When it comes to the interaction of two ore more parties with individual aims, it’s all about finding an appropriate strategy. In most cases, the individual aim boils down to detection of information about the general situation or about your opponents and improvement of your own position. This goal …
-
Automata and game theoretic models of computation
… investigate two finite state models of computation: automata and games on graphs. First we investigate the state complexity of finite word and tree automata from two directions. One direction is to study the interplay between non-deterministic automata (NFA) and deterministic automata (DFA) state …
-
Synchronous and quantum games: Graphical and algebraic methods
This is a mathematics thesis that contributes to an understanding of nonlocal games as formal objects. With that said, it does have connections to quantum physics and information theory. Nonlocal games are interactive protocols modelling two players attempting to win a game, by answering a pair of …
-
Degree Ramsey theory, game and Roman domination, and game saturation in graphs
… graph theory, emphasizing problems involving games on graphs. In Chapter 2, we study a variant of Ramsey theory, seeking Ramsey hosts with small maximum degree. We focus on finding such hosts for trees and cycles. In Chapter 3 we consider the ""on-line"" version of this problem. We model this …
-
Peg Solitaire on Trees with Diameter Four
In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all …
-
Oszacowania rozgrywanych liczb Ramseya
… wartości dla gry czworokąt vs. ścieżka. Ponadto prezentujemy metodę (pół)potencjału, która pozwala znajdować oszacowania rozgrywanych liczb Ramseya i dowodzimy, że jest ona uniwersalna. Pokazujemy też, że wiele ze znanych dowodów dotyczących rozgrywanych liczb Ramseya da się wyrazić w …