All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 52

Showing per page

Modeling shortest path games with Petri nets: a Lyapunov based theory

Julio Clempner (2006)

International Journal of Applied Mathematics and Computer Science

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...

Motion planning in cartesian product graphs

Biswajit Deb, Kalpesh Kapoor (2014)

Discussiones Mathematicae Graph Theory

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...

New results about impartial solitaire clobber

Eric Duchêne, Sylvain Gravier, Julien Moncel (2009)

RAIRO - Operations Research

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....

Note On The Game Colouring Number Of Powers Of Graphs

Stephan Dominique Andres, Andrea Theuser (2016)

Discussiones Mathematicae Graph Theory

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.

Note: The Smallest Nonevasive Graph Property

Michał Adamaszek (2014)

Discussiones Mathematicae Graph Theory

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...

On three-rowed chomp.

Brouwer, Andries E., Horváth, Gábor, Molnár-Sáska, Ildikó, Szabó, Csaba (2005)

Integers

On-line Ramsey theory.

Grytczuk, J.A., Hałuszczak, M., Kierstead, H.A. (2004)

The Electronic Journal of Combinatorics [electronic only]

Recursive algorithm for parity games requires exponential time

Oliver Friedmann (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

Recursive algorithm for parity games requires exponential time

Oliver Friedmann (2012)

RAIRO - Theoretical Informatics and Applications

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.

Signed Chip Firing Games and symmetric Sandpile Models on the cycles

Robert Cori, Thi Ha Duong Phan, Thi Thu Huong Tran (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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