Loading [MathJax]/extensions/MathZoom.js
In this paper we introduce a new modeling paradigm for shortest path games representation with Petri nets. Whereas previous works have restricted attention to tracking the net using Bellman's equation as a utility function, this work uses a Lyapunov-like function. In this sense, we change the traditional cost function by a trajectory-tracking function which is also an optimal cost-to-target function. This makes a significant difference in the conceptualization of the problem domain, allowing the...
Let G be an undirected graph with n vertices. Assume that a robot is placed on a vertex and n − 2 obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path...
Impartial Solitaire Clobber is a one-player version of the combinatorial game Clobber, introduced by Albert et al. in 2002.
The initial configuration of Impartial Solitaire Clobber is a graph, such that there is a stone placed on each of its vertex,
each stone being black or white. A move of the game consists in picking a stone, and clobbering an adjacent stone of the opposite color.
By clobbering we mean that the clobbered stone is removed from the graph, and replaced by the clobbering one....
We generalize the methods of Esperet and Zhu [6] providing an upper bound for the game colouring number of squares of graphs to obtain upper bounds for the game colouring number of m-th powers of graphs, m ≥ 3, which rely on the maximum degree and the game colouring number of the underlying graph. Furthermore, we improve these bounds in case the underlying graph is a forest.
A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that...
This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.
This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.
We investigate the Sandpile Model and Chip Firing Game and an extension of these models on cycle graphs. The extended model consists of allowing a negative number of chips at each vertex. We give the characterization of reachable configurations and of fixed points of each model. At the end, we give explicit formula for the number of their fixed points.
Currently displaying 21 –
40 of
52